滑动谜题

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开

1. 广度优先搜索

class Solution {
public:
    vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};
    int m; int n;
    int slidingPuzzle(vector<vector<int>>& board) {
        m = board.size(); n = board[0].size();
        set<string> s;
        queue<string> q;
        string str = vec_str(board);
        int count = 0;
        s.insert(str);
        q.push(str);
        while(!q.empty()){
            int len = q.size();
            for(int times=0;times<len;times++){
                string cur = q.front(); q.pop();
                if(check(cur)) return count;
                int index = cur.find('0');
                int x = index/n; int y =index%n;
                for(int i=0;i<dir.size();i++){//遍历四个方向
                    int nx = x + dir[i][0];
                    int ny = y + dir[i][1];
                    if(nx<0||nx==m||ny<0||ny==n) continue;
                    string temp = cur;
                    swap(temp[index],temp[nx*n+ny]);
                    if(s.count(temp)) continue;
                    s.insert(temp);
                    q.push(temp);
                }
            }
            count++;
        }
        return -1;
    }


    string vec_str(vector<vector<int>>& mat){
        string res;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                res.push_back(mat[i][j]+'0');
        return res;
    }
    bool check(string &s){
        return s=="123450";
    }
};