773 Sliding Puzzle

773. Sliding Puzzle

1. Question

On a 2x3board, there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0.

A move consists of choosing0 and a 4-directionally adjacent number and swapping it.

The state of the board is_solved_if and only if theboardis[[1,2,3],[4,5,0]].

Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.

Examples:

Input: board = [[1,2,3],[4,0,5]]

Output: 1

Explanation: Swap the 0 and the 5 in one move.

Input: board = [[1,2,3],[5,4,0]]

Output: -1

Explanation: No number of moves will make the board solved.

Input: board = [[4,1,2],[5,0,3]]

Output: 5

Explanation: 5 is the smallest number of moves that solves the board.

An example path:
After move 0: [[4,1,2],[5,0,3]]
After move 1: [[4,1,2],[0,5,3]]
After move 2: [[0,1,2],[4,5,3]]
After move 3: [[1,0,2],[4,5,3]]
After move 4: [[1,2,0],[4,5,3]]
After move 5: [[1,2,3],[4,5,0]]

Input: board = [[3,2,4],[1,5,0]]

Output: 14

Note:

• boardwill be a 2 x 3 array as described above.

• board[i][j]will be a permutation of[0, 1, 2, 3, 4, 5].

2. Implementation

(1) BFS

思路: 通过观察我们知道，每次搜索从0开始，0的移动方向有上下左右四种情况。因为我们以String的形式存储每一步的状态，比如board = [[1,2,3],[4,0,5]], 初始状态表示为 "123405", 可以得到0移动的方向有-1(左)， 1(右)，-3(上)，3(下)。但需要注意的是，在String里index 2和 index 3是相邻的，但在board里却不是，在判断位置是否valid时需要考虑这种特殊情况，具体可以看valid()函数的条件。这题的难点主要是通过观察发现状态转移的所有可能情况，剩下的都是很标准的BFS解法

class Solution {
    public int slidingPuzzle(int[][] board) {
        if (board == null || board.length == 0) {
            return -1;
        }

        String target = "123450";
        StringBuilder sb = new StringBuilder();

        for (int[] row : board) {
            for (int num : row) {
                sb.append(num);
            }
        }
        String start = sb.toString();

        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();

        visited.add(start);
        queue.add(start);

        int[] directions = {-1, 1, -3, 3};
        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                String curState = queue.remove();

                if (curState.equals(target)) {
                    return level;
                }

                int startIndex = curState.indexOf('0');

                for (int k = 0; k < 4; k++) {
                    int nextIndex = startIndex + directions[k];

                    if (isValid(startIndex, nextIndex)) {
                        char[] letters = curState.toCharArray();
                        swap(letters, startIndex, nextIndex);
                        String nextState = String.valueOf(letters);

                        if (!visited.contains(nextState)) {
                            queue.add(nextState);
                            visited.add(nextState);
                        }
                    }
                }
            }
            ++level;
        }
        return -1;
    }

    public boolean isValid(int index1, int index2) {
        if (index2 < 0 || index2 > 5 || index1 == 2 && index2 == 3 || index1 == 3 && index2 == 2) {
            return false;
        } 
        else {
            return true;
        }
    }

    public void swap(char[] letters, int i, int j) {
        char temp = letters[i];
        letters[i] = letters[j];
        letters[j] = temp;
    }
}

3. Time & Space Complexity

BFS: 时间复杂度((mn)!),m是board的行数，n是board的列数, 最多只有(mn)!的状态，空间复杂度O((mn)!)