Java数据结构BFS广搜法解决迷宫问题

import java.util.LinkedList;

import java.util.Scanner;

public class Main {

     //n*m的地图，(startx,starty)起点坐标，(endx,endy)终点坐标

     static int n, m, startx, starty, endx, endy;

     static int [][] map; //地图

     static boolean [][] vistied; //标记当前点是否已经走过

     static int [][] step = { { 1 , 0 }, { 0 , 1 }, { - 1 , 0 }, { 0 , - 1 } };

     /*

      * 上下左右移动遍历搜索 1 ,0 表示 x + 1 ，y + 0 向右移动，其他同理 如果为八向连通 则加上, { 1, 1 }, { 1, -1 }, {

      * -1, 1 }, { -1, -1 } 代表斜向移动

      */

     public static void main(String[] args) {

         Scanner sc = new Scanner(System.in);

         n = sc.nextInt();

         m = sc.nextInt();

         map = new int [n + 2 ][m + 2 ]; //+2是为了防止点在边界时，四方向移动造成下标出现-1越界。

         vistied = new boolean [n + 2 ][m + 2 ];

         // 录入数据图  下标（1~n）*（1~m）

         for ( int i = 1 ; i <= n; i++) {

             for ( int j = 1 ; j <= m; j++) {

                 map[i][j] = sc.nextInt();

             }

         }

         //录入起点和终点坐标

         startx = sc.nextInt();

         starty = sc.nextInt();

         endx = sc.nextInt();

         endy = sc.nextInt();

         bfs(startx, starty); //BFS广搜

     }

     private static void bfs( int x, int y) {

         point p = new point(x, y, 0 ); //初始化point类封装x，y坐标以及step步数

         LinkedList<point> queue = new LinkedList<point>(); //需要用到的队列

         queue.add(p); //将当前点入队列

         vistied[x][y] = true ; //标记成已访问

         boolean flag = false ; //是否达到终点标记

         //只要队列不为空，就说明还有路可走

         while (!queue.isEmpty()) {

             point first = queue.getFirst(); //取出队列的第一个点

             if (first.x == endx && first.y == endy) { //判断当前点是否与终点坐标重合

                 System.out.println(first.step); //打印需要走的步数

                 flag = true ; //标记已经到达终点

                 break ; //结束BFS

             }

             //未到达终点则进行上下左右四个方向移动

             for ( int i = 0 ; i < 4 ; i++) {

                 //横纵坐标变换实现位置移动

                 int newx = first.x + step[i][ 0 ];

                 int newy = first.y + step[i][ 1 ];

                 int newstep = first.step + 1 ; //每一动一次步数要+1

                 //判断移动后的新位置可以走，并且没走过

                 if (map[newx][newy] == 1 && vistied[newx][newy] == false ) {

                     point newp = new point(newx, newy, newstep); //封装数据

                     queue.add(newp); //入队列

                     vistied[newx][newy] = true ; //标记已经走过

                 }

             }

             queue.removeFirst(); //四个方向判断完成后，要将队首元素出列

         }

         if (!flag) //如果无法到达终点提示

             System.out.println( "NO" );

     }

}

//定义一个位置点的class，方便封装数据入队列

class point {

     int x;

     int y;

     int step; //从起点走到当前点需要走的步数

     public point( int x, int y, int step) {

         this .x = x;

         this .y = y;

         this .step = step;

     }

}