迷宫的最少步数and最短路径（BFS）-Toy模板网

这篇具有很好参考价值的文章主要介绍了迷宫的最少步数and最短路径（BFS）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题面

题目描述
一个迷宫由 R 行 C 列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。
输入
第一行是两个整数，R 和 C ，代表迷宫的行数和列数。（ 1≤R,C≤40 )
接下来是 R 行，每行 C 个字符，代表整个迷宫。空地格子用 . 表示，有障碍物的格子用 # 表示。
迷宫左上角和右下角都是 . 。
输出
输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。
计算步数要包括起点和终点。
样例

输入
5 5
..###
#....
#.#.#
#.#.#
#.#..
输出
9
链接：Link.

暴力搜索就行了

#include <bits/stdc++.h>
using namespace std;
int n , m , q[2500][4] , tail=1 , head=1;
int fx[5] ={0 , 0 , 1 , 0 , -1},fy[5] ={0 , 1 , 0 , -1 , 0};
char a[45][45];
int main(){
	scanf("%d%d" , &n , &m);
	for ( int i = 1 ; i <= n ; i++ )
		for ( int j = 1 ; j <= m ; j++ )
			cin >> a[i][j];
	q[1][1] = 1;
	q[1][2] = 1;
	q[1][3] = 1;
	int tx , ty;
	while ( head <= tail ){
		for ( int i = 1 ; i <= 4 ; i++ ){
			tx = q[head][1] + fx[i];
			ty = q[head][2] + fy[i];
			if ( a[tx][ty] == '.' ){
				a[tx][ty] = '#';
				q[++tail][1] = tx;
				q[tail][2] = ty;
				q[tail][3] = q[head][3] + 1;
				if ( tx == n && ty == m ){
					printf("%d" , q[tail][3]);
					return 0;
				}
			}
		}
		head++;
	}
	return 0;
}

题目描述

有 n×m 的迷宫，该迷宫有一个入口，一个出口。编写一程序打印一条从迷宫入口到出口的最短路径，黑色方块的单元表示走不通（用 1 表示），白色方块的内容表示走的通（用0 表示）。

只能往上下左右四个方向走，如果有最短路径，保证最短路径一定是唯一的，如果没有路径可以到达，则输出“no way”。

输入

第一行输入 2 个整数 n 和 m ( n 和 m 都是 10∼150 之间的整数)，代表迷宫的行数和列数；

接下来 n 行，每行有 m 个整数，11 代表不可走的点，00 代表可走的点；

接下来一行，有 2 个整数 s1 和 s2 代表入口的坐标；

接下来一行，有 2 个整数 e1 和 e2 代表出口的坐标；

本题数据上保证出发点和终点的值一定为 00，也就是不存在出发点和终点不能走的情况。

输出

输出从入口到出口的最短路径，如果没有路径可达输出“no way”。

样例文章来源地址https://www.toymoban.com/news/detail-634971.html

输入
8 5      
1 1 1 1 1  
0 0 0 0 1
1 1 1 0 1
1 0 0 0 1
1 0 0 1 1
1 0 0 0 1
1 1 1 0 1
1 0 0 0 1
2 1  
8 4
输出
(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,3)->(5,3)->(6,3)->(6,4)->(7,4)->(8,4)

注意每个节点的前驱和后继，存了前驱和后继才能找到最短路

#include <bits/stdc++.h>
using namespace std;
int n , m , q[40000][4] , tail=1 , head=1 , s1 , s2 , e1 , e2;
int fx[5] ={0 , 0 , 1 , 0 , -1},fy[5] ={0 , 1 , 0 , -1 , 0};
int a[160][160];
void print(int t){ //递归输出
	if(t > 1)
		print(q[t][3]);
	printf("(%d,%d)" , q[t][1] , q[t][2]);
	if ( t < tail )
		printf("->");
}
int main(){
	scanf("%d%d" , &n , &m);
	for ( int i = 1 ; i <= n ; i++ )
		for ( int j = 1 ; j <= m ; j++ )
			cin >> a[i][j];
	scanf("%d%d%d%d" , &s1 , &s2 , &e1 , &e2);
	q[1][1] = s1;
	q[1][2] = s2;
	q[1][3] = 0;
	int tx , ty;
	while(head <= tail){
		for ( int i = 1 ; i <= 4 ; i++ ){
			tx = q[head][1] + fx[i];
			ty = q[head][2] + fy[i];
			if ( tx >= 1 && tx <= n && ty >= 1 && ty <= m && a[tx][ty] == 0 ){
				q[++tail][1] = tx;
				q[tail][2] = ty;
				q[tail][3] = head;
				a[tx][ty] = 1;
				if( tx == e1 && ty == e2 ){
					print(tail);
					return 0;
				}
			}
		}
		head++;
	}
	printf("no way");
	return 0;
}

到了这里，关于迷宫的最少步数and最短路径（BFS）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！