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

刚一看到这道题，说用BFS我可以get大概idea, 但具体怎么实现，还是懵逼的，具体懵逼的点在于，怎么把这么一个二维矩阵转化为图和BFS的数据结构，也就是说，把具体问题建立模型的见多识广上还有点弱鸡。

先说解题思想，再说怎么用数据结构代入具体问题。

思路：0所在的地方就是出发点，0可以swap的邻居就是联通的边。0每swap一步，图的状态就改变一次，图有初始状态和目标状态。0每swap一次，就和目标状态对比一次，一旦匹配成功，既可以返回步数。此时如何让步数最小呢，那么就是BFS，这也很可以想，因为BFS把每一层的情况都遍历到了，但凡这一层有的就能够返回，说明步数是最少的。

数据结构：棋盘是一个二维数组，这一格二维数组就表示了一个状态。

set<vector<vector<int>>> visited : 用来记录所有访问过的状态

queue<pair<vector<vector<int>>, vector<int>>> q : 用来做BFS，pair里面存状态和"0"的对应坐标

int res 记录访问了几层

vector<vector<int>> dirs = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}} : 用来标记0可以走的方向，每次都用这几个值来计算新的0的坐标， int x = zero[0] + dir[0], int y = zero[1] + dir[1] 

随后就是BFS常规操作。

语法点：

1. q.front() 不是指针或者iterator，而是开头的元素，所以用 .first, .second， q.begin(), q.end() 是iterator

2. swap(a[i][j], b[i][j]), 原来可以直接swap 二维数组

3. q.push({board, {i,j}}), {board, {i, j}} 可以直接初始化pair, 而不需要pair(.....). 

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        int res = 0;
        vector<vector<int>> target = {{1,2,3}, {4,5,0}};
        set<vector<vector<int>>> visited;
        queue<pair<vector<vector<int>>, vector<int>>> q;
        vector<vector<int>> dirs = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        
        for (int i = 0; i<2; i++)
        { 
            for (int j = 0; j<3; j++)
            {
               if (board[i][j] == 0)
               {
                   q.push({board, {i,j}});
               }
            }
        }
        
        while(!q.empty())
        {
            // BFS finish visit one level, q size is changing, so 
            // take the initial one
            int size = q.size();
            for (int i = 0; i<size; i++)
            {
                auto cur = q.front().first;
                auto zero = q.front().second;
                q.pop();
                if (cur == target) return res;
                visited.insert(cur);
                for (auto dir : dirs)
                {
                    int x = zero[0] + dir[0], y = zero[1] + dir[1];
                    if (x < 0 || x >=2 || y < 0 || y >= 3) continue;
                    vector<vector<int>> tmp = cur;
                    swap(tmp[zero[0]][zero[1]], tmp[x][y]);
                    if (visited.count(tmp) > 0) continue;
                    q.push({tmp, {x,y}});
                }
            }
            ++res;
        }
        return -1;
    }
};