773

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        // Get the moves where 0 can move.. idx->vector<int>.
        vector<vector<int>> moves = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
        string end = "123450";
        unordered_map<string, bool> visited;

        // Init start string with distance 0.
        string begin = "";
        for(int i = 0; i < board.size(); i++) {
            for(int j = 0; j < board[0].size(); j++) {
                begin += to_string(board[i][j]);
            }
        }

        // Init queue of <string, int> : <state, distance>
        queue<pair<string, int>> q;
        q.push({begin, 0});
        visited[begin] = true;

        while(!q.empty()){
            auto curr = q.front();
            q.pop();
            string current = curr.first;

            // Reached end, return the number of moves.
            if(current == end) return curr.second;

            // Find index of 0 and find all possible next moves
            int idx = current.find("0");
            for(auto i: moves[idx]){
                string next = current;
                swap(next[idx], next[i]);
                // If next state not visited, push it in queue.
                if(!visited.count(next)){
                    visited[next] = true;
                    q.push({next, curr.second+1});
                }
            }
        }
        // If not possible to reach end state;
        return -1;
    }
};