[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;
        Queue<int[][]> srcQ = new LinkedList();
        Queue<int[][]> destQ = new LinkedList();
        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;
    }
    
}