# 773 Sliding Puzzle

## 773. [Sliding Puzzle](https://leetcode.com/problems/sliding-puzzle/description/)

## 1. Question

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

A move consists of choosing`0` and a 4-directionally adjacent number and swapping it.

The state of the board is\_solved\_if and only if the`board`is`[[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:**

* `board`will 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解法

```java
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)!)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/algorithm-practice/leetcode/breadth-first-search/773-sliding-puzzle.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.