[LeetCode] 773. Sliding Puzzle

Solution

Bidirectional BFS

Set two queues, src queue and dest queue. Init src queue with input board, and dest queue with final state [[1,2,3],[4,5,0]].

When both queues are not empty, expand the queue with smaller size until searching process meet at some point where expansion from src finds a state has been discovered by dest direction.

Code

``````class Solution {
public int slidingPuzzle(int[][] board) {
if(toInt(board) == 123450) return 0;
HashMap<Integer, Integer> srcSteps = new HashMap();
HashMap<Integer, Integer> destSteps = new HashMap();
srcQ.offer(board);
destSteps.put(toInt(new int[][]{{1,2,3},{4,5,0}}), 0);
destQ.offer(new int[][]{{1,2,3},{4,5,0}});
srcSteps.put(toInt(board), 0);
int step = -1;
while(srcQ.size() > 0 && destQ.size() > 0 ) {
if (srcQ.size() <= destQ.size()) {
step = expand(srcQ, srcSteps, destSteps);
} else {
step = expand(destQ, destSteps, srcSteps);
}

if (step != -1) {
return step;
}
}

return step;

}

private int expand(Queue<int[][]> q, HashMap<Integer, Integer> src, HashMap<Integer, Integer> dest) {
int steps = -1;
int[][] cur = q.poll();
int[][] dirs = new int[][]{{0,1},{0, -1}, {1, 0}, {-1, 0}};
for (int i = 0; i < 2; i++) {
for(int j = 0; j < 3; j++) {
if (cur[i][j] == 0) {
for (int[] dir : dirs) {
int nx = i + dir[0];
int ny = j + dir[1];

int[][] tmp = new int[2][3];
for(int x = 0; x < 2; x++) {
for (int y = 0; y < 3; y++) {
tmp[x][y] = cur[x][y];
}
}

if (nx >= 0 && nx < 2 && ny >= 0 && ny < 3 ) {
tmp[i][j] = tmp[nx][ny];
tmp[nx][ny] = 0;
//System.out.println(toInt(tmp));
if (dest.get(toInt(tmp)) != null) {
return dest.get(toInt(tmp)) + src.get(toInt(cur)) + 1;
}

if (src.get(toInt(tmp)) != null) {
continue;
}

src.put(toInt(tmp), src.get(toInt(cur)) + 1);
q.offer(tmp);

}
}
}
}
}
return steps;
}

private int toInt(int[][] board){
int ans = 0;
for(int i = 0; i < 2; i++) {
for(int j= 0; j < 3; j++) {
ans = ans * 10 + board[i][j];
}
}
return ans;
}

}``````