[773] 滑动谜题

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.
一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
示例：

输入：board = [[1,2,3],[4,0,5]]
输出：1
解释：交换 0 和 5 ，1 步完成

输入：board = [[1,2,3],[5,4,0]]
输出：-1
解释：没有办法完成谜板

输入：board = [[4,1,2],[5,0,3]]
输出：5
解释：
最少完成谜板的最少移动次数是 5 ，
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]

输入：board = [[3,2,4],[1,5,0]]
输出：14

提示：

• board 是一个如上所述的 2 x 3 的数组.
• board[i][j] 是一个 [0, 1, 2, 3, 4, 5] 的排列.

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {

        if(board.size() != 2 || board[0].size() != 3) return 0;
        int dirs[4][2]={{-1,0},{0, 1},{1, 0}, {0, -1}};
        queue<string> q;
        unordered_map<string, int> dis; 
        q.push(toState(board));
        dis[toState(board)] = 0;
        while(!q.empty()){
            string cur = q.front();
            q.pop();
            // cout<<cur<<" "<<dis[cur]<<endl;
            if(cur == "123450"){
                return dis[cur];
            }
            int zero_index = 0;
            for(int i = 0; i < 6; i++){
                if(cur[i] == '0'){
                    zero_index = i;
                    break;
                }
            }
            vector<string> nextStrings;
            for(int i = 0; i< 4; i++){
                // int next_index = zero_index + dirs[i][0] * 3 + dirs[i][1];
                int next_x = zero_index / 3 + dirs[i][0];
                int next_y = zero_index % 3 + dirs[i][1];
                if(inArea(next_x, next_y)){
                    int next_index = next_x * 3 + next_y;
                    string nextS = swap(cur, zero_index, next_index);
                    if(dis.find(nextS) == dis.end()){
                        q.push(nextS);
                        dis[nextS] = dis[cur] + 1;
                    }

                }
            }
        }
        return -1;
    }
    bool inArea(int x, int y){
        return x>=0 && x < 2 && y >= 0 && y < 3;
    }
    string swap(string orig, int i, int j){
        string temp = orig;
        char t = temp[i];
        temp[i] = temp[j];
        temp[j] = t;
        return temp;
    }
    string toState(vector<vector<int>>& board){
        string res(6, '0');
        for(int i = 0; i< board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                int index = i * board[0].size() + j;
                res[index] = board[i][j] + '0';
            }
        }
        return res;
    }
};