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

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

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

&nbsp;
Example 1:

Input: board = [[1,2,3],[4,0,5]]
Output: 1
Explanation: Swap the 0 and the 5 in one move.


Example 2:

Input: board = [[1,2,3],[5,4,0]]
Output: -1
Explanation: No number of moves will make the board solved.


Example 3:

Input: board = [[4,1,2],[5,0,3]]
Output: 5
Explanation: 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]]


&nbsp;
Constraints:


	board.length == 2
	board[i].length == 3
	0 &lt;= board[i][j] &lt;= 5
	Each value board[i][j] is unique.


class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        def findNei(board):
            directs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
            boards = []
            for i in range(2):
                for j in range(3):
                    if board[i][j] == 0:
                        for dr, dc in directs:
                            tmp = [row.copy() for row in board]
                            r, c = i + dr, j + dc
                            if r in range(2) and c in range(3):
                                tmp[r][c], tmp[i][j] = tmp[i][j], tmp[r][c]
                                boards.append(tmp)
            return boards

        visited = set()
        target = [[1, 2, 3], [4, 5, 0]]
        if board == target:
            return 0
        rows, cols = len(board), len(board[0])
        q = collections.deque()
        step = 1

        for row in range(rows):
            for col in range(cols):
                if board[row][col] == 0:
                    boards = findNei(board)
                    for b in boards:
                        if b == target:
                            return step
                        visited.add(tuple([tuple(row) for row in b]))
                        q.append(b)
                    break

        while q:
            step += 1
            for _ in range(len(q)):
                b = q.popleft()
                boards = findNei(b)
                for b in boards:
                    if b == target:
                        return step
                    t = tuple([tuple(row) for row in b])
                    if t not in visited:
                        visited.add(t)
                        q.append(b)

        return -1
class Solution {
    int [][] dir={{1,3},{0,2,4},{1,5},{0,4},{1,3,5},{2,4}};
    public int slidingPuzzle(int[][] board) {

        String tar="123450";

        String src="";

        for(int i =0;i<board.length;i++){
            for(int j=0;j<board[i].length;j++){
                src+=board[i][j];
            }
        }

       HashSet<String> visited=new HashSet<>();

        visited.add(src);
        int level=0;
        ArrayDeque<String> q=new ArrayDeque<>();
        q.add(src);
        while(q.size()!=0){
            int t=q.size();

            while(t-->0){
                String rem=q.remove();

                if(rem.equals(tar)){
                    return level;
                }

                int idx=-1;

                for(int i=0;i<rem.length();i++){
                    if(rem.charAt(i)=='0'){
                        idx=i;
                        break;
                    }
                }

                for(int i =0;i<dir[idx].length;i++){
                    String str=swapEle(rem,idx,dir[idx][i]);

                    if(!visited.contains(str)){
                        q.add(str);
                        visited.add(str);
                    }
                }
            }
            level++;
        }

        return -1;
    }

    public String swapEle(String rem,int i,int j){
        StringBuilder sb=new StringBuilder(rem);

        sb.setCharAt(i,rem.charAt(j));
        sb.setCharAt(j,rem.charAt(i));

        return sb.toString();
    }
}
class Node{
public:
int row;
int col;
vector<vector<int>>state;
    };

class Solution {
public:

int slidingPuzzle(vector<vector<int>>& board) {

    vector<vector<int>>target={{1,2,3},{4,5,0}};
    queue<Node>q;
    int n=2;
    int m=3;
    vector<vector<int>>dir={{1,0},{-1,0},{0,1},{0,-1}};

    for(int i=0;i<board.size();i++)
        for(int j=0;j<board[0].size();j++){
            if(board[i][j]==0){
                q.push({i,j,board});
                break;
            }
        }

    set<vector<vector<int>>>set;
    set.insert(q.front().state);
    int ladder=0;
    while(!q.empty()){
       int size=q.size();
        for(int i=0;i<size;i++){
            Node curr=q.front();
            q.pop();
            if(curr.state==target)
                return ladder;

            int row=curr.row;
            int col=curr.col;
            for(auto &x:dir){
                int r=x[0]+row;
                int c=x[1]+col;

                if(r<n && r>=0 && c<m && c>=0 ){
                    swap(curr.state[r][c],curr.state[row][col]) ;
                    if(set.find(curr.state)==set.end()){
                        set.insert(curr.state);
                        q.push({r,c,curr.state});
                    }
                     swap(curr.state[r][c],curr.state[row][col]) ;

                }

            }

        }
        ladder++;

    }
    return -1;

}
};
/**
 * @param {number[][]} board
 * @return {number}
 */

class BoardState {
    constructor(board, currStep) {
        this.board = this.copyBoard(board);
        this.boardString = this.flatToString(board);
        this.emptyIndex = this.findIndexOf0(board);
        this.currStep = currStep;
    }
    findIndexOf0(board) {
        for(let i = 0; i < board.length; i++) {
            for (let j = 0; j < board[i].length; j++) {
                if(board[i][j] === 0) return [i, j];
            }
        }
        return null;
    }
    copyBoard(board) {
        const newBoard = [];
        board.forEach((row) => {
             newBoard.push([...row]);
        });
        return newBoard;
    }
    flatToString(board) {
        let str = '';
        for(let i = 0; i < board.length; i++) {
            for (let j = 0; j < board[i].length; j++) {
                str += board[i][j];
            }
        }
        return str;
    }
}
var slidingPuzzle = function(board) {
    let queue = [new BoardState(board, 0)];
    let set = new Set();
    const x = board.length, y = board[0].length;
    const switchMoves = [[1, 0], [0, 1], [-1, 0], [0, -1]];
    let slide = (i, j, newi, newj, currBoardState) => {
        if (newi < 0 || newj < 0 || newi >= x || newj >= y) {
            return null;
        }
        const newBoard = currBoardState.copyBoard(currBoardState.board);
        const temp = newBoard[i][j];
        newBoard[i][j] = newBoard[newi][newj];
        newBoard[newi][newj] = temp;
        const newBoardState = new BoardState(newBoard, currBoardState.currStep + 1);
        return newBoardState
    }
    while(queue.length > 0) {
        const currBoardState = queue.shift();
        set.add(currBoardState.boardString);
        if(currBoardState.boardString === '123450') {
            return currBoardState.currStep;
        }
        const [i, j] = currBoardState.emptyIndex;
        switchMoves.forEach((move) => {
            const newBoardState = slide(i, j, i + move[0], j + move[1], currBoardState);
            if (newBoardState && !set.has(newBoardState.boardString)) {
                queue.push(newBoardState);
            }
        });
    }
    return -1;
};
Sliding Puzzle