亲宝软件园·资讯

展开

Java 迷宫问题

求不脱发 人气:0

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

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rGC5LiN6ISx5Y-R,size_20,color_FFFFFF,t_70,g_se,x_16

2. 思路分析

基本思想

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

具体步骤

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

2)结点 p 入队列

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

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

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

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

代码实现

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 运用到了队列。

加载全部内容

相关教程
猜你喜欢
用户评论