BFS广度优先搜索解决迷宫问题
BFS广度优先搜索解决迷宫问题
BFS广度优先搜索解决迷宫问题
1、题目描述
给定一个
的网格迷宫G。G的每个格子要么是道路，要么是障碍物(道路用1表示，障碍物用2表示)。
一直迷宫的入口位置为
，出口位置为
。问从入口道出口，最多要走多少个格子。
输入描述
输入第1行包含两个整数N,M，分别表示迷宫的大小
接下来输入一个
的矩阵。若
表示其为道路，否则表示其为障碍物。
最后一行输入四个整数
，表示入口的位置和出口的位置。
输出描述
输出仅一行，包含一个整数表示答案。
若无法从入口道出口，则输出-1。
输入示例
5 4
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 1 2
1 1 4 3输出示例
82、解题思路
迷宫示意图如下所示：图中start为起点，end为终点，方格中的2为障碍物。
我们需要先给出四个方向，并用如下代码代理上下左右四个方向
static int[][] dirs={
{0,1},//右
{1,0},//下
{0,-1},//左
{-1,0}//上
}; 我们的基本思想是按照BFS的基本操作，将迷宫看成一个无向图，每一个格子为一个节点，如果两个格子相邻且都是道路，则这两个格子之间有一条边。先将初始结点入队列，刚开始队列头节点为(1,1,0)即(x,y,step)，用一个Point类来模拟。x和y代表坐标，step代表走的步数。然后不断地从队列中取出队首节点，然后再扩展它的邻居节点，再将它的邻居节点入队列(需要做一些条件判断)。如果扩展到终点节点，则搜索结束，返回step即可。
我们可以使用一个visited来记录节点是否被访问过。我们每从队列中取出一个节点的时候，将它的所有扩展结点(不包括墙和被访问过的)加入队列，同时更新这些扩展节点的step，改成当前节点的step+1,并将访问状态设置为true。如果扩展到终点节点，则搜索结束。如果队列为空的时候仍未扩展到终点节点，则搜索失败，没找到终点。
手动模拟队列进出过程如下，第一个图中标的数字为step。start处的step=0，end出的step=7。
3、代码实现
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
//定义四个方向
static int[][] dirs={
{0,1},//右
{1,0},//下
{0,-1},//左
{-1,0}//上
};
public static void main(String[] args) {
//输入
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int[][] a=new int[n+1][m+1]; //迷宫
boolean[][] visited=new boolean[n+1][m+1]; //记录访问状态
LinkedList<Point> queue=new LinkedList<>();//申请队列
for (int i = 1; i <=n ; i++) {
for (int j = 1; j <=m ; j++) {
a[i][j]=scan.nextInt();
}
}
//起点和终点坐标
int startX = scan.nextInt();
int startY = scan.nextInt();
int endX = scan.nextInt();
int endY = scan.nextInt();
boolean flag=false;//标记是否找到终点
//BFS
Point start = new Point(startX, startY, 0);
//起点入队
queue.add(start);
visited[startX][startY]=true;//设置起点已经被访问
while(!queue.isEmpty()){
//队首元素出队
Point point = queue.remove();
int x = point.x;
int y = point.y;
if(x==endX&&y==endY){ //找到终点
System.out.println(point.step);//直接输出step
flag=true;//标记找到终点
break;
}
//进行四个方向的扩展
for (int[] dir : dirs) {
int tx = x + dir[0]; //扩展点x坐标
int ty = y + dir[1]; //扩展点y坐标
//检查扩展节点坐标是否超出边界
if(tx<1||tx>n||ty<1||ty>m){
continue;
}
//检查扩展节点是否是墙壁
if(a[tx][ty]==2){ //是墙壁就跳过该节点
continue;
}
//检查扩展节点是否已经被访问过
if(visited[tx][ty]){
continue;
}
if(a[tx][ty]==1&& !visited[tx][ty]){//如果是空地且未访问，则入队
queue.add(new Point(tx,ty,point.step+1));//步数为队首步数+1
visited[tx][ty]=true; //设置这个入队的点已经访问
}
}
}
//没找到终点
if(!flag){
System.out.println("没找到终点");
}
}
}
//节点类，其实用数组模拟也可以，这里为了模仿一下结构体
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;
}
}
这里我们用了一个
Point类来模拟每个节点，节点属性为(x,y,step)