经典BFS模板题

参考代码:

import java.util.LinkedList;
import java.util.Scanner;
public class Main {
    public static class Q{
        int x;
        int y;
        int demp;
    }
    public static void main(String[] args) {
        Scanner scanner= new Scanner(System.in);
        int f[][]={{1,0},{0,1},{0,-1},{-1,0}};
        int n=scanner.nextInt();
        int m=scanner.nextInt();
        int gx=0,gy=0;//起点
        int mx=0,my=0;//终点
        LinkedList<Q> que=new LinkedList<Main.Q>();
        char[][] arr=new char[n][m];
        int[][] book=new int[n][m];
        for (int i = 0; i < arr.length; i++) {
            String str=scanner.next();
            for (int j = 0; j < arr[i].length; j++) {
                arr[i][j]=str.charAt(j);
                if (arr[i][j]=='@') {
                    gx=i;gy=j;
                }
                if (arr[i][j]=='*') {
                    mx=i;my=j;
                }
            }
        }
        book[gx][gy]=1;//标记起始位置
        Q q=new Q();
        q.x=gx;
        q.y=gy;
        q.demp=0;
        que.add(q);//入队
        //开始BFS
        int lu=0;
        while (que.size()!=0) {//只要队列不为空就继续循环
            Q sr=que.poll();//取出队列顶部的值
            if (sr.x==mx&&sr.y==my) {
                lu=sr.demp;
                break;
            }
            for (int i = 0; i < 4; i++) {
                int tx=sr.x+f[i][0];
                int ty=sr.y+f[i][1];
                if (tx>=0&&tx<n&&ty>=0&&ty<m&&arr[tx][ty]!='#'&&book[tx][ty]==0) {
                    book[tx][ty]=1;
                    Q temp=new Q();
                    temp.x=tx;
                    temp.y=ty;
                    temp.demp=sr.demp+1;
                    que.add(temp);
                }
            }
        }
        if (lu==0) {
            System.out.println("Impossibility!");
        }else {
            System.out.println(lu);
        }
    }
 }