/*
knakul853
6:44 pm
Tuesday, 9 June 2020 (IST)
*/
class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        // 1 2 3
        // 4 5 0
        //123456

        vector<vector<int>>moves{{1, 3},{0, 2, 4}, {1, 5}, {0,4}, {3, 1, 5}, {2, 4}};

        string end = "123450";

        string start="";
        for(auto v: board)
        {
            for(auto num : v)
            {
                start += to_string(num);
            }
        }

        queue<string>q;
        unordered_map<string, int>mp;
        mp[start] = 1;
        q.push( start );
        int ans = 0;

        while( !q.empty() )
        {
            int sz = (int)q.size();
            for( int i=0;i<sz;i++ )
            {
            auto node =  q.front();

            if(node == end ) return ans;
            q.pop();

            int id = (int)node.find("0");

                for( int num : moves[id] )
                {
                    swap(node[ num ], node[ id ]);
                    if(!mp.count(node))
                    {
                        mp[node] = 1;
                        q.push( node );
                    }
                    swap(node[ num ], node[ id ]);
                }
            }

            ans++;

        }

        return -1;

    }
};