773. Sliding Puzzle

https://leetcode.com/problems/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防止重复遍历。

// @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

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