<p>On an <code>2 x 3</code> board, there are five tiles labeled from <code>1</code> to <code>5</code>, and an empty square represented by <code>0</code>. A <strong>move</strong> consists of choosing <code>0</code> and a 4-directionally adjacent number and swapping it.</p>

<p>The state of the board is solved if and only if the board is <code>[[1,2,3],[4,5,0]]</code>.</p>

<p>Given the puzzle board <code>board</code>, return <em>the least number of moves required so that the state of the board is solved</em>. If it is impossible for the state of the board to be solved, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/29/slide1-grid.jpg" style="width: 244px; height: 165px;" />
<pre>
<strong>Input:</strong> board = [[1,2,3],[4,0,5]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> Swap the 0 and the 5 in one move.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/29/slide2-grid.jpg" style="width: 244px; height: 165px;" />
<pre>
<strong>Input:</strong> board = [[1,2,3],[5,4,0]]
<strong>Output:</strong> -1
<strong>Explanation:</strong> No number of moves will make the board solved.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/29/slide3-grid.jpg" style="width: 244px; height: 165px;" />
<pre>
<strong>Input:</strong> board = [[4,1,2],[5,0,3]]
<strong>Output:</strong> 5
<strong>Explanation:</strong> 5 is the smallest number of moves that solves the board.
An example path:
After move 0: [[4,1,2],[5,0,3]]
After move 1: [[4,1,2],[0,5,3]]
After move 2: [[0,1,2],[4,5,3]]
After move 3: [[1,0,2],[4,5,3]]
After move 4: [[1,2,0],[4,5,3]]
After move 5: [[1,2,3],[4,5,0]]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>board.length == 2</code></li>
	<li><code>board[i].length == 3</code></li>
	<li><code>0 &lt;= board[i][j] &lt;= 5</code></li>
	<li>Each value <code>board[i][j]</code> is <strong>unique</strong>.</li>
</ul>


class Node {
    public:
        string code;
        Node* next;
        int depth;

        Node(string input_code, int input_depth){
            code = input_code;
            depth = input_depth;
            next = nullptr;
        }
};

class Queue {

    public:

        int count;
        Node* head;
        Node* tail;

        Queue(){
            count = 0;
            head = nullptr;
            tail = nullptr;
        }

        void push(string code, int depth){

            Node* newNode = new Node(code, depth);

            if (count==0){
                head = newNode;
                tail = newNode;
            } else{
                tail->next = newNode;
                tail = newNode;
            }

            count = count + 1;
        }

        Node* pop(){

            //string code;
            //code = head->code;
            Node* temp = head;
            head = head->next;
            count = count - 1;

            return temp;
        }
        bool isEmpty(){
            return count == 0;
        }
};

void str2int(string s, int* board_arr){

    int cnt = 0;
    for (int i=0; i<6; i++){
        board_arr[cnt]= s[i]-'0';
        if (s[i] == '0'){
            board_arr[6] = cnt;
        }
        cnt += 1;
    }
}

void int2str(int* array, string& s){
    s = "";
    for (int i=0; i<6;i++){
        s += to_string(array[i]);   
    }

}

void swap(int* arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

bool strcmp(string a, string b){

    for(int i=0;i<6;i++){
        if(a[i]!=b[i]){
            return false;
        }
    }
    return true;
}

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

        string target = "123450";
        bool visit[6][6][6][6][6][6] = {false};

        string board_str = "";
        int a[7];
        int cnt = 0;
        for (int i=0; i<2;i++){
            for (int j=0; j<3; j++){
                board_str += to_string(board[i][j]);   
            }
        }
        
        str2int(board_str, a);
        if (strcmp(board_str, target)) return 0;

        visit[a[0]][a[1]][a[2]][a[3]][a[4]][a[5]] = true;

        int depth = 0;

        Queue queue;
        
        queue.push(board_str, depth);

        while(!queue.isEmpty()){
            Node* a = queue.pop();

            int arr [7]; 
            str2int(a->code, arr);
            int pos = arr[6];
            //cout << a->depth << " "<< pos << endl;

            //down
            if(pos<3){
                swap(arr, pos, pos+3);
                if (!visit[arr[0]][arr[1]][arr[2]][arr[3]][arr[4]][arr[5]]){
                    string s;
                    int2str(arr, s);
                    if (strcmp(s, target)){
                        return (a->depth) + 1;
                    }
                    queue.push(s, (a->depth) + 1);
                    visit[arr[0]][arr[1]][arr[2]][arr[3]][arr[4]][arr[5]] = true;
                }
                swap(arr, pos, pos+3);
            }

            //up
            if(3<=pos && pos<6){
                swap(arr, pos, pos-3);
                if (!visit[arr[0]][arr[1]][arr[2]][arr[3]][arr[4]][arr[5]]){
                    string s;
                    int2str(arr, s);
                    if (strcmp(s, target)){
                        return (a->depth) + 1;
                    }
                    queue.push(s, (a->depth) + 1);
                    visit[arr[0]][arr[1]][arr[2]][arr[3]][arr[4]][arr[5]] = true;
                }
                swap(arr, pos, pos-3);
            }

            //right
            if(pos==0 || pos==1 || pos==3 || pos==4 ){
                swap(arr, pos, pos+1);
                if (!visit[arr[0]][arr[1]][arr[2]][arr[3]][arr[4]][arr[5]]){
                    string s;
                    int2str(arr, s);
                    if (strcmp(s, target)){
                        return (a->depth) + 1;
                    }
                    queue.push(s, (a->depth) + 1);
                    visit[arr[0]][arr[1]][arr[2]][arr[3]][arr[4]][arr[5]] = true;
                }
                swap(arr, pos, pos+1);
            }
            //left
            if(pos==1 || pos==2 || pos==4 || pos==5 ){
                swap(arr, pos, pos-1);
                if (!visit[arr[0]][arr[1]][arr[2]][arr[3]][arr[4]][arr[5]]){
                    string s;
                    int2str(arr, s);
                    if (strcmp(s, target)){
                        return (a->depth) + 1;
                    }
                    queue.push(s, (a->depth) + 1);
                    visit[arr[0]][arr[1]][arr[2]][arr[3]][arr[4]][arr[5]] = true;
                }
                swap(arr, pos, pos-1);
            }

        }

        return -1;   
    }
};


12759