描述
在一个3x3的网格中，放着编号1到8的8块板，以及一块编号为0的空格。
一次移动可以把空格0与上下左右四邻接之一的板子交换。
给定初始和目标的板子排布，返回到目标排布最少的移动次数。
如果不能从初始排布移动到目标排布，返回-1.
在线评测地址：领扣题库官网
样例1
输入:
[
[2,8,3],
[1,0,4],
[7,6,5]
]
[
[1,2,3],
[8,0,4],
[7,6,5]
]
输出:
4
解释:
[ [
[2,8,3], [2,0,3],
[1,0,4], --> [1,8,4],
[7,6,5] [7,6,5]
] ]
[ [
[2,0,3], [0,2,3],
[1,8,4], --> [1,8,4],
[7,6,5] [7,6,5]
] ]
[ [
[0,2,3], [1,2,3],
[1,8,4], --> [0,8,4],
[7,6,5] [7,6,5]
] ]
[ [
[1,2,3], [1,2,3],
[0,8,4], --> [8,0,4],
[7,6,5] [7,6,5]
] ]样例2
输入:
[[2,3,8],[7,0,5],[1,6,4]]
[[1,2,3],[8,0,4],[7,6,5]]
输出:
-1使用单向 BFS 算法
public class Solution {
/**
* @param init_state: the initial state of chessboard
* @param final_state: the final state of chessboard
* @return: return an integer, denote the number of minimum moving
*/
public int minMoveStep(int[][] init_state, int[][] final_state) {
String source = matrixToString(init_state);
String target = matrixToString(final_state);
Queue<String> queue = new LinkedList<>();
Map<String, Integer> distance = new HashMap<>();
queue.offer(source);
distance.put(source, 0);
while (!queue.isEmpty()) {
String curt = queue.poll();
if (curt.equals(target)) {
return distance.get(curt);
}
for (String next : getNext(curt)) {
if (distance.containsKey(next)) {
continue;
}
queue.offer(next);
distance.put(next, distance.get(curt) + 1);
}
}
return -1;
}
public String matrixToString(int[][] state) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
sb.append(state[i][j]);
}
}
return sb.toString();
}
public List<String> getNext(String state) {
List<String> states = new ArrayList<>();
int[] dx = {0, 1, -1, 0};
int[] dy = {1, 0, 0, -1};
int zeroIndex = state.indexOf('0');
int x = zeroIndex / 3;
int y = zeroIndex % 3;
for (int i = 0; i < 4; i++) {
int x_ = x + dx[i];
int y_ = y + dy[i];
if (x_ < 0 || x_ >= 3 || y_ < 0 || y_ >= 3) {
continue;
}
char[] chars = state.toCharArray();
chars[x * 3 + y] = chars[x_ * 3 + y_];
chars[x_ * 3 + y_] = '0';
states.add(new String(chars));
}
return states;
}
}使用双向 BFS 算法。可以把这份代码当模板背诵。
public class Solution {
/**
* @param init_state: the initial state of chessboard
* @param final_state: the final state of chessboard
* @return: return an integer, denote the number of minimum moving
*/
public int minMoveStep(int[][] init_state, int[][] final_state) {
String source = matrixToString(init_state);
String target = matrixToString(final_state);
if (source.equals(target)) {
return 0;
}
Queue<String> forwardQueue = new ArrayDeque<>();
Set<String> forwardSet = new HashSet<>();
forwardQueue.offer(source);
forwardSet.add(source);
Queue<String> backwardQueue = new ArrayDeque<>();
Set<String> backwardSet = new HashSet<>();
backwardQueue.offer(target);
backwardSet.add(target);
int steps = 0;
while (!forwardQueue.isEmpty() && !backwardQueue.isEmpty()) {
steps++;
if (extendQueue(forwardQueue, forwardSet, backwardSet)) {
return steps;
}
steps++;
if (extendQueue(backwardQueue, backwardSet, forwardSet)) {
return steps;
}
}
return -1;
}
private boolean extendQueue(Queue<String> queue,
Set<String> set,
Set<String> targetSet) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String curt = queue.poll();
for (String next : getNext(curt)) {
if (set.contains(next)) {
continue;
}
if (targetSet.contains(next)) {
return true;
}
queue.offer(next);
set.add(next);
}
}
return false;
}
public String matrixToString(int[][] state) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
sb.append(state[i][j]);
}
}
return sb.toString();
}
public List<String> getNext(String state) {
List<String> states = new ArrayList<>();
int[] dx = {0, 1, -1, 0};
int[] dy = {1, 0, 0, -1};
int zeroIndex = state.indexOf('0');
int x = zeroIndex / 3;
int y = zeroIndex % 3;
for (int i = 0; i < 4; i++) {
int x_ = x + dx[i];
int y_ = y + dy[i];
if (x_ < 0 || x_ >= 3 || y_ < 0 || y_ >= 3) {
continue;
}
char[] chars = state.toCharArray();
chars[x * 3 + y] = chars[x_ * 3 + y_];
chars[x_ * 3 + y_] = '0';
states.add(new String(chars));
}
return states;
}
}更多题解参考：九章官网solution
