# 773. Sliding Puzzle

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]`.

给一个由打乱顺序的123450组成的两行三列矩阵，每次能让0和周围swap，问最短多少步能让整个有序。像简单版华容道。最短步数，不是BFS就是DP。这道题直接无脑BFS就能以很快运行时间AC。把当前的阵型encoding成string，把遍历过的放进visited防止重复遍历。

```cpp
// @lc code=start
class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        const int M = board.size(), N = board[0].size();
        string start, goal;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                // convert to char
                start += (board[i][j] + '0');
                goal += (i * N + j + 1) % (M * N) + '0';
            }
        }
        if (start == goal) return 0;
        vector<vector<int>> dirs({{-1, 0}, {1, 0}, {0, -1}, {0 , 1}});
        unordered_set<string> visited{start};
        int step = 0;
        queue<string> q;
        q.push(start);
        while (!q.empty()) {
            ++step;
            for (int c = q.size() - 1; c >= 0; --c) {
                const auto &s = q.front();
                int p = s.find('0');
                int i = p / N;
                int j = p % N;
                for (const auto &d : dirs) {
                    int x = i + d[0], y = j + d[1];
                    if (x >= 0 && x < M && y >= 0 && y < N) {
                        int pp = x * N + y;
                        string t(s);
                        swap(t[p], t[pp]);
                        if (visited.count(t)) continue;
                        if (t == goal) return step;
                        visited.insert(t);
                        q.push(t);
                    }
                }
                q.pop();
            }
        }
        return -1;
    }
};
// @lc code=end


```

```python
class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        M, N = len(board), len(board[0]) 
        s = ''.join(str(num) for row in board for num in row)
        q = collections.deque([(s, s.index('0'))])
        v = {s}
        dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        res = 0
        while q:
            size = len(q)
            for _ in range(size):
                t, p = q.popleft()
                if t == '123450':
                    return res
                for d in dirs:
                    x, y = p // N + d[0], p % N + d[1]
                    if x >= 0 and x < M and y >= 0 and y < N:
                        ch = [c for c in t]
                        p2 = x * N + y
                        ch[p] = ch[p2]
                        ch[p2] = '0'
                        s = ''.join(ch)
                        if s not in v:
                            v.add(s)
                            q.append((s, p2))
            res += 1
        return -1
                
```


---

# 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://hao-fu-1.gitbook.io/oj/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.