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

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

目录1.例题题目描述输入输出测试数据2. 思路分析基本思想具体步骤代码实现3.BFS小结求解思路：注意

1.例题

题目描述

迷宫由 n 行 m 列的单元格组成，每个单元格要么是空地，要么是障碍物。其中1表示空地，可以走通，2表示障碍物。给定起点坐标startx,starty以及终点坐标endx，endy。现请你找到一条从起点到终点的最短路径长度。

输入

第一行包含两个整数n,m（1<=n,m<=1000）。接下来 n 行，每行包含m个整数（值1或2），用于表示这个二维迷宫。接下来一行包含四个整数startx，starty，endx，endy，分别表示起点坐标和终点坐标。

输出

如果可以从给定的起点到终点，输出最短路径长度，否则输出NO。

测试数据

输入

5 4

1 1 2 1

1 1 1 1

1 1 2 1

1 2 1 1

1 1 1 2

输出

7

2. 思路分析

基本思想

这道题属于一道较为经典的BFS图的广度优先搜索算法例题。类似于一个分层搜索的过程，广度优先搜索需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序访问这些结点的邻接结点。即从给定的起点开始向四周扩散，判断是否能够到达终点，如果不能，就继续BFS广搜，直到能够到达终点或者将所有结点遍历完一遍。在搜索前定义一个flag变量用来标记是否到达终点。

具体步骤

1）访问初始结点 p 并标记结点 p 为已访问。

2）结点 p 入队列

3）当队列非空时，继续执行，否则算法结束。

4）出队列取得队头结点 first

5）查找结点 first 的第一个方向的邻接结点 newp 。

6）若结点 first 的邻接结点 newp 不存在，则转到步骤3：否则循环执行以下三个步骤：

6.1若结点 newp 尚未被访问并且可以走通，则访问结点 newp 并标记为已访问。

6.2结点 newp 入队列

6.3查找结点 first 的继 newp 邻接结点后的下个邻接结点 newp ．转到步骤6

代码实现

import java.util.LinkedList;

import javpLbnXDvuvda.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 queue = new LinkedList();//需要用到的队列

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;

}

}

3.BFS小结

求解思路：

将队首结点可拓展的点入队，如果没有可拓展的点，将队首结点出队。重复以上步骤，直到到达目标位置或者队列为空。

注意

bfs先找到的一定是最短的。但是如果是加权边的话这样就会出问题了，bfs传回的是经过 边数 最少的解，但是因为加权了，这个解到根节点的 距离 不一定最短。 比如1000+1000是只有两段，1+1+1+1有4段，由于bfs返回的经过边数最少的解，这里会返回总长度2000的那个解，显然不是距离最短的路径。BFS 运用到了队列。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。