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 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;
	}
}

3.BFS小结

求解思路:

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

注意

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

到此这篇关于Java数据结构BFS广搜法解决迷宫问题的文章就介绍到这了,更多相关Java 迷宫问题内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 如何利用JAVA实现走迷宫程序

    本Demo使用三个类 一个Test类 一个自定义的Stack类 一个自定义的Queue类 可以实现的功能: 1.对于一个写在文本文件中的迷宫,能够将其转换为二维数组用广度优先搜索实现查找最短路径 2.可以不定义迷宫的入口和出口,能自动查找到出入口 前提是要有一个对应路径的.txt文件 这里举个例子吧,我的是"F:/1号迷宫(0,18).txt"路径下 运行结果 示例代码 注释写的很详细,这里就不多赘述了 package com; import java.io.BufferedReade

  • Java递归实现迷宫游戏

    目录 1.问题由来 2.问题的描述 3.思路分析 4.代码实现 5.结果输出 1.问题由来 迷宫实验是取自心理学的一个古典实验.在该实验中,把一只老鼠从一个无顶大盒子的门放入,在盒中设置了许多墙,对行进方向形成了多处阻挡.盒子仅有一个出口,在出口处放置一块奶酪,吸引老鼠在迷宫中寻找道路以到达出口.对同一只老鼠重复进行上述实验,一直到老鼠从入口到出口,而不走错一步.老鼠经多次试验终于得到它学习走迷宫的路线. 2.问题的描述 有一个迷宫地图,有一些可达的位置,也有一些不可达的位置(障碍.墙壁.边界)

  • Java数据结构 递归之迷宫回溯案例讲解

    问题介绍: 用二维数组表示一个迷宫,设置迷宫起点和终点,输出迷宫中的一条通路 实现思路: 二维数组表示迷宫: 0表示路且未走过.1表示墙.2表示通路,3表示已经走过但走不通 设置寻路方法setWay,传入地图和坐标参数 默认方向策略:下.右.上.左 假定传入的店没有走过且可以走通,将其值置为2,然后向下寻路,也就是将坐标 (i + 1, j) 传入寻路方法中 进行递归寻路,向下移动后,再次按照方向策略进行寻路,即再向下寻路,直到遇到死路,即下右左均走不通(因为将走过的路置为2,故向上也走不通,即

  • 详解Java利用深度优先遍历解决迷宫问题

    目录 什么是深度优先 一个简单的例子 程序实现 什么是深度优先 什么是深度,即向下,深度优先,即向下优先,一口气走到底,走到底发现没路再往回走. 在算法实现上来讲,深度优先可以考虑是递归的代名词,深度优先搜索必然需要使用到递归的思路. 有的人可能会说了,我可以用栈来实现,以迭代的方式,那么问题来了,栈这种数据结构,同学们认为是否也囊括了递归呢?Java语言的方法区本身也是实现在一个栈空间上的. 一个简单的例子 我们以一个简单的迷宫为例,以1代表墙,0代表路径,我们构造一个具有出入口的迷宫. 1

  • Java实现简单的迷宫游戏详解

    目录 前言 主要设计 功能截图 代码实现 窗口布局 核心算法 总结 前言 人类建造迷宫已有5000年的历史.在世界的不同文化发展时期,这些奇特的建筑物始终吸引人们沿着弯弯曲曲.困难重重的小路吃力地行走,寻找真相.迷宫类小游戏应运而生.在游戏中,迷宫被表现为冒险舞台里,藏有各式各样奇妙与谜题或宝藏的危险区域.型态有洞窟.人工建筑物.怪物巢穴.密林或山路等.迷宫内有恶徒或凶猛的生物(真实存在或想像物体都有)徘徊,其中可能会有陷阱.不明设施.遗迹等. <简单迷宫>游戏是用java语言实现,采用了sw

  • Java实现经典游戏复杂迷宫

    目录 前言 主要设计 功能截图 代码实现 总结 前言 人类建造迷宫已有5000年的历史.在世界的不同文化发展时期,这些奇特的建筑物始终吸引人们沿着弯弯曲曲.困难重重的小路吃力地行走,寻找真相.迷宫类小游戏应运而生.在游戏中,迷宫被表现为冒险舞台里,藏有各式各样奇妙与谜题或宝藏的危险区域.型态有洞窟.人工建筑物.怪物巢穴.密林或山路等.迷宫内有恶徒或凶猛的生物(真实存在或想像物体都有)徘徊,其中可能会有陷阱.不明设施.遗迹等. <复杂迷宫>游戏是用java语言实现,采用了swing技术进行了界面

  • 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),用于表示这个二维

  • java数据结构之二分查找法 binarySearch的实例

    java数据结构之二分查找法 binarySearch的实例 折半查找法,前提是已经排好序的数组才可查找 实例代码: public class BinarySearch { int[] bArr; public void setArr(int[] bArr){ this.bArr=bArr; } public static void main(String[] args) { int arrLength=16; int[] bArr=new int[arrLength]; System.out.

  • java 数据结构与算法 (快速排序法)

    快速排序法: 顾名思议,快速排序法是实践中的一种快速的排序算法,在c++或对java基本类型的排序中特别有用.它的平均运行时间是0(N log N).该算法之所以特别快,主要是由于非常精练和高度优化的内部循环.快速排序是对冒泡法的一种改进.通过一趟排序将要排序的的数据分割成独立的两部分,其中一部分的所有数据都比另一部分所有的数据要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 示意图: 这里 定义最左边元素 为left 最右边元素为ri

  • Python 实现递归法解决迷宫问题的示例代码

    迷宫问题 问题描述: 迷宫可用方阵 [m, n] 表示,0 表示可通过,1 表示不能通过.若要求左上角 (0, 0) 进入,设计算法寻求一条能从右下角 (m-1, n-1) 出去的路径. 示例图: 此示例图基本参数为: m:对应 x 轴n:对应 y 轴 绿色线代表期望输出的路径 算法思路 标记当前所在位置 如果此时所在位置为终点,说明可以到达终点,退出递归: 否则,则存在 4 种可能的移动方向即上.下.左.右,遍历这 4 个方向,如果这 4 个方向存在相邻值为 0 的点,则将当前点坐标标记为该相

  • Python使用回溯法子集树模板解决迷宫问题示例

    本文实例讲述了Python使用回溯法解决迷宫问题.分享给大家供大家参考,具体如下: 问题 给定一个迷宫,入口已知.问是否有路径从入口到出口,若有则输出一条这样的路径.注意移动可以从上.下.左.右.上左.上右.下左.下右八个方向进行.迷宫输入0表示可走,输入1表示墙.为方便起见,用1将迷宫围起来避免边界问题. 分析 考虑到左.右是相对的,因此修改为:北.东北.东.东南.南.西南.西.西北八个方向.在任意一格内,有8个方向可以选择,亦即8种状态可选.因此从入口格子开始,每进入一格都要遍历这8种状态.

  • java迷宫算法的理解(递归分割,递归回溯,深搜,广搜)

    最近这学期做了一个java迷宫的课程设计,这里代码及其算法逻辑就分享出来. 首先简单的说一下其中我使用的算法(自动生成地图:递归分割法.递归回溯法:寻找路径:深度优先.广度优先算法) 递归分割法: 地图外面一圈被墙围住,然后在空白区域生成十字墙壁,再随机选择三面墙,将其打通,这样就能保证迷宫的流动性,再分别对刚才分好的四个区域以同样的方式执行分割,一直递归下去,直到空间不足以分割就return. 递归回溯法: 递归回溯法与深度优先算法在大致算法上其实差不多,具体只有一些细微的差别,都是通过判断当

  • Java数据结构之实现哈希表的分离链接法

    哈希表的分离链接法 原理 Hash Table可以看作是一种特殊的数组.他的原理基本上跟数组相同,给他一个数据,经过自己设置的哈希函数变换得到一个位置,并在这个位置当中放置该数据.哦对了,他还有个名字叫散列 0 1 数据1 数据2 就像这个数组,0号位置放着数据1,1号位置放数据2 而我们的哈希表则是通过一个函数f(x) 把数据1变成0,把数据2变成1,然后在得到位置插入数据1和数据2. 非常重要的是哈希表的长度为素数最好!! 而且当插入数据大于一半的时候我们要进行扩充!!! 冲突问题产生 现在

  • Java 数据结构哈希算法之哈希桶方式解决哈希冲突

    一. 实现形式一(键值对只能为整数) 我们可以先实现一个比较简单的哈希表,使用java中解决哈希冲突的方法,即哈希桶(开散列)方式实现,其中注意: 可以使用内部类方式定义节点 负载因子默认为0.75 因为我们使用的是哈希桶方式解决哈希冲突,所以在我们扩容成功之后,原来桶中的数据得重新哈希计算出新的位置,不然就和原来桶中的数据的位置不一样了 相关代码如下 public class HashBucket { static class Node {//使用内部类方式定义节点 public int ke

  • Java通过递归算法解决迷宫与汉诺塔及八皇后问题

    目录 1.递归的重要规则 2.递归的三个案例 1.老鼠出迷宫 2.汉诺塔 3.八皇后 1.递归的重要规则 在执行一个方法时,就创建一个新的受保护的独立空间(栈空间). 方法的局部变量时独立的,不会相互影响. 如果方法中使用的是应用类型变量(比如数组,对象),就会共享该引用类型的数据. 递归必须向退出递归的条件逼近,否则就是无限递归. 当一个方法执行完毕,或者遇到return,就会返回,遵循谁调用,就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕. 2.递归的三个案例 1.老鼠出

随机推荐