A standard BFS Leetcode 773 Sliding Puzzle

773. Sliding Puzzle

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        int n = 2, m = 3;
        vector<pair<int, int>> dirs = {{0,1},{0,-1},{1,0},{-1,0}}; 
        string goal = "123450";
        queue<pair<int, string>> Q;
        int zero = 0;
        string curr = "";
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 3; ++j)
            {
                if (board[i][j] == 0) zero = 3*i + j;
                curr += to_string(board[i][j]);
            }    
        unordered_set<string> seen;
        Q.emplace(zero, curr);
        seen.insert(curr);
        int ret = 0;
        if (curr == goal) return 0;
        while (!Q.empty())
        {
            auto len = Q.size();
            while(len--)
            {
                auto [idx, curr] = Q.front(); Q.pop();
                auto i = idx/3, j = idx%3;
                for (auto [di, dj] : dirs)
                {
                    auto r = i + di;
                    auto c = j + dj;
                    if (r>=0 && r<2 && c >=0 && c <3)
                    {
                        auto new_idx = r*3 + c;
                        string new_state = curr;
                        swap(new_state[new_idx], new_state[idx]);
                        if (new_state == goal)return ret + 1;
                        if (!seen.count(new_state))
                        {
                            seen.insert(new_state);
                            Q.emplace(new_idx, new_state);
                            
                        }
                        
                    }
                }
            }
            ret++;
        }
        return -1;
    }
};