773. Sliding Puzzle

这题也是一道经典的BFS题，
每个状态是图上的node，每个node可能有四条边连到其他的node。
然后就是一个图遍历的问题。
这里 把每个node的状态转换成一个数字，然后用的时候再转换回来。
我看到有个把它一维化的做法，觉得不太直观，二维就二维呗，多写几行吧。
用DFS？肯定可以做，不过求最短路径的问题傻X才用DFS呢。
看代码，这题不是hard呀，不知道为什么标成hard，可能状态转换比较繁琐吧。

class Solution {
    public int slidingPuzzle(int[][] board) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        
        int curCode = getCode(board);
        if (curCode == 123450) return 0;
        queue.offer(curCode);
        visited.add(curCode);
        
        int level = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int code = queue.poll();
                for (int nextCode : getNextCode(code)) {
                    if (visited.add(nextCode)) {
                        if (nextCode == 123450) return level;
                        queue.offer(nextCode);
                    }
                }
            }
            level++;
        }
        return -1;
    }
    int[][] OFFSETS = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    private List<Integer> getNextCode(int code) {
        int[][] board = new int[2][3];
        int[] zeroLocation = null;
        for (int r = 1; r >= 0; r--) {
            for (int c = 2; c >= 0; c--) {
                board[r][c] = code % 10;
                code /= 10;
                if (board[r][c] == 0) {
                    zeroLocation = new int[]{r, c};
                }
            }
        }
        List<Integer> ans = new ArrayList<>();
        int cr = zeroLocation[0], cc = zeroLocation[1];
        for (int[] os : OFFSETS) {
            int nr = cr + os[0], nc = cc + os[1];
            if (nr >= 0 && nc >= 0 && nr < 2 && nc <3) {
                swap(board,nr, nc, cr, cc);
                ans.add(getCode(board));
                swap(board,nr, nc, cr, cc);
            }
        }
        return ans;
    }
    private void swap(int[][] board, int r, int c, int nr, int nc) {
        int tmp = board[r][c];
        board[r][c] = board[nr][nc];
        board[nr][nc] = tmp;
    }
    
    private int getCode(int[][] board) {
        int code = 0;
        for (int r = 0; r < 2; r++) {
            for (int c = 0; c < 3; c++) {
                code *= 10;
                code += board[r][c];
            }
        }
        return code;
    }
}