说明：本代码由b站网友：万众烟火不及你 编写

仅供学习参考，转载请标明出处

代码难免存在bug，请网友海涵，以下为代码部分

本代码中，地图边界为0，与麦克老师的实例中的边界为1不同，请注意

BFS.java :

package BFS;


import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//广度优先搜索
//问题：给定一个迷宫（n*m）每个空地要么是空地要么是障碍物，找到一条最短路径
/*
* 算法：入队起点，队首节点可以拓展的点入队，如果没有可以入队的点则出队，重复，直到达到目的或者队列为空
* */
public class BFS {
    public static void main(String[] args) {
        Queue queue = new LinkedList<>();  //队列，先入先出
        int[][] map = new int[100][100];   //地图，1表示为空地，否则不可达
        int[][] v = new int[100][100];  //访问数组
        int[] dx = {0,1,0,-1};  //方向数组
        int[] dy = {1,0,-1,0};  //右，下，左，上
        boolean flag = false;  //是否有解
        //输入
        Scanner sc = new Scanner(System.in);
        int n,m,start_x,start_y,end_x,end_y;
        System.out.println("输入行和列：");
        n = sc.nextInt();   //n行，纵轴
        m = sc.nextInt();   //m列，横轴
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                map[i][j] = sc.nextInt();
            }
        }
        System.out.println("输入起始坐标：");
        start_x = sc.nextInt();
        start_y = sc.nextInt();
        System.out.println("输入终点坐标：");
        end_x = sc.nextInt();
        end_y = sc.nextInt();
        sc.close();

        //BFS
        Point start = new Point();
        start.x = start_x;
        start.y = start_y;
        start.step = 0;
        start.path = "";
        queue.offer(start);  //起点入队
        v[start_x][start_y] = 1; //已被访问

        while (!queue.isEmpty()){  //队列非空
            int x = queue.element().x;
            int y = queue.element().y;
            if(x == end_x && y ==end_y){  //到达终点
                System.out.println("最短路径为："+queue.element().path+" 长度为："+queue.element().step);
                flag = true;
                break;
            }
            //四个方向进行试探
            for (int i = 0; i <= 3; i++){
                int tx,ty;
                tx = x + dx[i];
                ty = y + dy[i];
                if(tx >= 0 && ty >=0 && tx <= n && ty <= m && map[tx][ty] == 1 && v[tx][ty] == 0){  //map为空地且未被访问
                    Point temp = new Point();
                    temp.x = tx;
                    temp.y = ty;
                    temp.step = queue.element().step+1;
//                    System.out.println("当前坐标："+temp.x+" "+temp.y);
                    switch (i){
                        case 0:
                            temp.path = queue.element().path+"右";
                            break;
                        case 1:
                            temp.path = queue.element().path+"下";
                            break;
                        case 2:
                            temp.path = queue.element().path+"左";
                            break;
                        case 3:
                            temp.path = queue.element().path+"上";
                            break;
                    }
                    queue.offer(temp);
                    v[tx][ty] = 1;
                }
            }
            queue.poll();  //拓展完毕后队首需要出队
        }
        if(!flag){
            System.out.println("no solution");
        }
    }
}

point.java :

(point.java相当于视频中的struct)

package BFS;

public class Point {
    int x;
    int y;
    int step;  //所需步数
    String path;   //路径
}

测试用例：

-----以下为输入------
输入行和列：
5 5
1 1 1 1 1
1 1 1 1 1
1 1 2 1 1
1 2 1 1 1
1 1 1 1 1
输入起始坐标：
0 0
输入终点坐标：
3 2
-----以下为输出-----
最短路径为：右右右下下下左 长度为：7