class Solution {
    public int slidingPuzzle(int[][] board) {
        /* Q9 of graph playlist , we make a allowed swaps for every index and call bfs
            for intial string and whenever initial string is equal to target string we return
            that level
        */

        //making a hashset of visited strings
        HashSet<String> set = new HashSet<>();

        String target = "123450";
        
        //making initial string
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ;i < board.length ; i++){
            for(int j = 0 ; j < board[0].length ; j++){
                sb.append(board[i][j]);
            }
        }
        String initial = sb.toString();

        //making a q and adding initial to the q
        LinkedList<String> q= new LinkedList<>();
        q.addLast(initial);

        //make 2d array for allowed swaps for every index
        int [][] swaps = {{1,3} , {0,4 ,2}, {1,5} , {0,4}, {1 ,3 ,5} , {2 , 4}};

        //applying bfs and returning level
        int level = 0;

        while(q.size() > 0){
            int size = q.size();
            while(size-- > 0){
                String rem = q.pop();
                
                // System.out.println(target + "->" + rem);
                if(rem.equals(target))
                return level;

                //find 0th index in current string
                int idx = rem.indexOf('0');

                // System.out.println(idx);
                //applying swaps 
                for(int swap : swaps[idx]){
                    String swapped = swap(idx , swap , rem);
                    // System.out.println(swapped);

                    if(set.contains(swapped) == false){
                        set.add(swapped);
                        q.add(swapped);
                    }
                    
                }
            }
            level++;
        }
        return -1;
    }

    public String swap (int i , int j , String str){
        StringBuilder sb = new StringBuilder(str);

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

        return sb.toString();
    }
}