广度优先搜索解决最短路径问题 题解 2079: 找寻小妖

解题思路: 注释都敲好了。不懂自己debug跑一遍就豁然开朗。这套代码同可解决题目 2107: 误落迷宫2

注意事项: 

参考代码:

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * @author fzy
 * @create 2021/10/12 11:58
 **/
public class Main {
    static  char [][] data;
    static  boolean [][] isVisited;//与data一一对应 记录当前节点是否被访问
    static int n,m;//n行，m列
    //四个方向 右 下 左 上
    static int[] dx={0,1,0,-1};
    static int[] dy={1,0,-1,0};
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        n=input.nextInt();
        m=input.nextInt();
        data=new char[n][m];
        isVisited=new boolean[n][m];
        input.nextLine();
        int startX=0,startY=0;//起始位置
        for (int i = 0; i < n; i++) {
            String str=input.nextLine();
            for (int j = 0; j < m; j++) {
                data[i][j]=str.charAt(j);
                if(str.charAt(j) == '@'){
                    //记录起点位置
                    startX=i;
                    startY=j;
                }
            }
        }
        
        Node huba=bfs(startX,startY, '*');
        if(huba != null){
            System.out.println(huba.step);
        }else{
            System.out.println("Impossibility!");
        }
        
    }

    static class Node{
        int x;//横坐标
        int y;//纵坐标
        int step;//到当前节点 需要的步数

        public Node(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }
    
    //广度优先搜索 第一条路径必为最短路径
    //起始点 终点字符
    public  static Node bfs(int x,int y,char key){
        LinkedList queue=new LinkedList();//双向队列
        //后插 起点进队列
        queue.addLast(new Node(x,y,0));
        isVisited[x][y]=true;//标记该节点已经访问过
        //队列为空时 表示所有路径都以遍历完 且没找到胡巴
        while (!queue.isEmpty()){
            //弹出队头节点表示以该节点为起始节点 继续向四个方向进行搜索
            Node node = queue.removeFirst();
            if(data[node.x][node.y]== key){
                //表示找到目的地(胡巴) 返回该节点
                return node;
            }
            //搜索该节点 四个方向的邻节点 如果可访问 则后插入队列
            for (int i=0;i=0 && nextX=0 && nextY<m //边界判断
                    && !isVisited[nextX][nextY] //这个相邻节点没被访问过
                    && data[nextX][nextY] != '#' //这个相邻节点可以被访问
                ){
                    isVisited[nextX][nextY]=true;//标记该相邻节点已经被访问
                    queue.addLast(new Node(nextX,nextY,node.step+1));
                }
            }
        }
        return null;
    }
}