BFS广度优先遍历——Acwing 844. 走迷宫

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;


public class Main{

    static int n,m,N=110;
    static int [][]p=new int[N][N];     //存储原始地图
    static boolean [][]state=new boolean[N][N];  //每个点是否走过
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String []s=br.readLine().split(" ");
        n=Integer.parseInt(s[0]);
        m=Integer.parseInt(s[1]);
        for (int i = 1; i <=n; i++) {
            s=br.readLine().split(" ");
            for (int j =1; j <=m; j++) {
                p[i][j]=Integer.parseInt(s[j-1]);
            }
        }
        bfs();
        br.close();
    }

    private static void bfs() {
        int x=1,y=1;
        Queue<Point> q=new ArrayDeque<>();  //创建队列存储走过的每一个点
        q.add(new Point(x,y,0));      //首先把第一个点存进队列
        int []dy={0,-1,0,1};
        int []dx={-1,0,1,0};
        while (!q.isEmpty()){
            Point head=q.poll();      //取出队首元素
            if(head.x==n &&head.y==m){   //如果走到出口
                System.out.println(head.step);
                return;
            }
            for (int i = 0; i < 4; i++) {   //往四个方向走
                x= head.x+dx[i]; y= head.y+dy[i];
                if(x>0 &&x<=n &&y>0 &&y<=m &&!state[x][y] &&p[x][y]==0){ //如果还没有走过并且可以走
                 state[x][y]=true;
                 q.add(new Point(x,y, head.step+1));
                }
            }
        }
    }

    static class Point{
        int x,y,step;
        Point(){
        }

        public Point(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }
}

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String []s=br.readLine().split(" ");
        String start="";
        for (int i = 0; i < s.length; i++) {
            start+=s[i];
        }
        System.out.println(bfs(start));
        br.close();
    }

    private static Integer bfs(String start) {
        String end="12345678x";
        Queue<String> q=new ArrayDeque<>(); //存储所有状态
        Map<String,Integer> state=new HashMap<>(); //存储每个状态得交换次数
        q.add(start);
        state.put(start,0); //存初始状态
        int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0};//四个方向
        while (!q.isEmpty()){//枚举所有状态
            String head=q.poll();//取出头一个状态并向前寻找（head过程中不能修改，因为有四次变化 而位置都是map[t]+1）
            if(head.equals(end))    return state.get(head);
            int k=head.indexOf('x'); //找到x所在的下标
            int x=k/3,y=k%3;
            for (int i = 0; i < 4; i++) {
                int a=x+dx[i],b=y+dy[i];//变化状态之后x的下标
                if(a>=0 &&a<3 &&b>=0 &&b<3){  //变换后不出界的就是可用的
                char []ch=head.toCharArray();//字符串里面不能交换所以就到字符数组里
                swap(ch,k,a*3+b);
                String s=new String(ch);
                if(state.get(s)==null){//如果这个状态没出现过就存储这个状态
                    q.add(s);
                    state.put(s,state.get(head)+1);
                }
                }
            }
        }
        return -1;
    }

    private static void swap(char[] arr, int x, int y) {
        char c=arr[x];
        arr[x]=arr[y];
        arr[y]=c;
    }
}