This is the 26th day of my participation in the genwen Challenge

The title

On a 2 x 3 board, there are five tiles, represented by numbers 1 to 5, and a vacancy represented by a 0.

A move is defined as choosing 0 to swap with an adjacent number (up, down, left, and right).

Finally when the board result is [[1,2,3],[4,5,0]] the puzzle board is solved.

Given the initial state of a puzzle board, return the minimum number of moves it can take to solve the puzzle board, or -1 if it cannot be solved.

  • Example:
Input: board = [[1,2,3],[4,0,5]] output: 1 ,1,2 board = [[4], [5,0,3]] output: 5: at least finish the board at least mobile number is 5, a mobile path: not mobile: [,1,2 [4], [5,0,3]] move 1: [,1,2 [4], [0,5,3]] move 2 times: ,5,3 [[0], [4]] move three times: [,0,2 [1], [4,5,3]] move four times: [[1 0], [4,5,3]] move 5 times: ,5,0 [[1, 2, 3], [4]] : input board = [4-trichlorobenzene [3], [1,5,0]] output: 14Copy the code

Tip:

  • A board is an array of 2 x 3 as described above.
  • A board[I][j] is a permutation of [0, 1, 2, 3, 4, 5].

Their thinking

  1. Use a string to represent the state of the puzzle board
Board = [[1,2,3],[4,0,5]] 123405 Is represented by the character string 123405Copy the code

So each string represents a state of the puzzle board

  1. Breadth-first search

Using the queue to achieve breadth-first search, according to the position of 0, the 0 and the surrounding digits are exchanged, thus deriving several cases to join the queue

code

class Solution {
    public void swagg(char[] tar,int x,int y) {
        char temp=tar[x];
        tar[x]=tar[y];
        tar[y]=temp;
    }
    public int slidingPuzzle(int[][] board) {

        StringBuilder stringBuilder=new StringBuilder();
        for (int i=0; i<board.length; i++)for (int j=0; j<board[0].length; j++) { stringBuilder.append(board[i][j]); } Set<String> set=new HashSet<>();
        Queue<String> queue=new LinkedList<>();
        queue.add(stringBuilder.toString());
        int res=0;
         String s=null;
        while(! queue.isEmpty()) {int cur=queue.size();
            for (int i=0; i<cur; i++) { s = queue.poll();if(s.equals("123450"))  return res;
                char[] th=s.toCharArray();
                for (int j=0; j<6; j++) {if(th[j]=='0')
                    {
                        int x=j%3,y=j/3;
                        if(y==1)
                        {
                            swagg(th,j,x);
                            String temp=new String(th);
                            if(! set.contains(temp)) queue.add(temp); set.add(temp); swagg(th,j,x); }else {
                            swagg(th,j,x+3);
                            String temp=new String(th);
                            if(! set.contains(temp)) queue.add(temp); set.add(temp); swagg(th,j,x+3);
                        }
                        if(x>0)
                        {
                            swagg(th,j,j-1);
                            String temp=new String(th);
                            if(! set.contains(temp)) queue.add(temp); set.add(temp); swagg(th,j,j-1);
                        }
                        if(x<2)
                        {
                            swagg(th,j,j+1);
                            String temp=new String(th);
                            if(! set.contains(temp)) queue.add(temp); set.add(temp); swagg(th,j,j+1);
                        }
                      
                    }
                }
            }
            res++;
        }
       return -1; }}Copy the code