Description

Submission

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        queue<string> q;

        string s;
        for(int i = 0; i < 2; ++i) {
            for(int j = 0; j < 3; ++j) {
                s += ('0' + board[i][j]);
            }
        }

        q.push(s);
        int ret = 0;

        vector<int> dirs {-1, 0, 1, 0, -1};
        set<string> visited;

        for(; !q.empty(); ++ret) {
            int n = q.size();
            

            for(int t = 0; t < n; ++t) {
                string cur = q.front();
                q.pop();
                
                if(cur == "123450") return ret;

                if(visited.count(cur)) continue;
                visited.insert(cur);

                int idx = 0;
                for(int i = 0; i < 6; ++i) {
                    if(cur[i] == '0') {
                        idx = i;
                        break;
                    }
                }

                int x = idx / 3;
                int y = idx % 3;

                for(int i = 0; i < 4; ++i) {
                    int newX = x + dirs[i];
                    int newY = y + dirs[i+1];

                    if(newX >= 2 || newX < 0 || newY < 0 || newY >= 3) continue;
                    int newIdx = newX * 3 + newY;

                    swap(cur[idx], cur[newIdx]);
                    if(!visited.count(cur))
                        q.push(cur);
                    swap(cur[idx], cur[newIdx]);
                }
            }
        }

        return -1;
    }
};