广度优先搜索bfs

提示：本文大部分是手写的，由于手的问题（不想打），大家就看图片把

C++搜索02-BFS

引入&样例1、2讲解

总结

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

例题

1.Luogu B3625 迷宫寻路

题目描述

机器猫被困在一个矩形迷宫里。

迷宫可以视为一个 n * m 矩阵，每个位置要么是空地，要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。

机器猫初始时位于 (1, 1) 的位置，问能否走到 (n, m) 位置。

输入格式

第一行，两个正整数 n,m。

接下来 n 行，输入这个迷宫。每行输入一个长为 $m$ 的字符串，# 表示墙，. 表示空地。

输出格式

仅一行，一个字符串。如果机器猫能走到 (n, m)，则输出 Yes；否则输出 No。

禁止只输出Yes或No骗分！禁止只输出Yes或No骗分！禁止只输出Yes或No骗分！

样例 #1

样例输入 #1

1
2
3
4
3 5
.##.#
.#...
...#.

样例输出 #1

1
Yes

提示

样例解释

路线如下：(1,1)to (2,1) to (3,1) to (3,2)to (3,3) to (2, 3) to (2, 4) to (2, 5) to (3, 5)

数据规模与约定

对于 $100\%$ 的数据，保证 1 <= n, m <= 100，且 (1,1) 和 (n, m) 均为空地。

题解（这次真的是我写的了）

P3625 迷宫寻路题解

题意：

我们根据长和宽输入迷宫，判断能否达到$(n,m)$
位置，如果可以输出Yes，否则输出No

解法：

用BFS进行搜索，搜索可行路线，找到一条去终点的路线

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
struct node
{
	int x;
	int y;
	int s;//步数 
} que[10001];
int head,tail,r,s,p,q;
char c[1001][1001];//保存地图
bool flag;//标记是否达到目标点，0未到，1已到
int a[4]={-1,1,0,0},b[4]={0,0,-1,1};//可走的组合
bool f[1001][1001];//记录已走的点
void bfs()
{
	while(head<tail)//队列不为空时操作
	{
		for(int i=0;i<=3;i++)//枚举四个方向
		{
			int xx=que[head].x+a[i];
			int yy=que[head].y+b[i];
			if(xx>=1&&xx<=r&&yy>=1&&yy<=s&&c[xx][yy]=='.'&&!f[xx][yy])//判断x,y下一步是否可走且是否走过
			{
				f[xx][yy]=1;//标记已走
				que[tail].x=xx;
				que[tail].y=yy; //更新xx和yy的值
				que[tail].s=que[head].s+1;//步数是父亲的步数+1
				tail++; 
			}
			if(xx==p&&yy==q)//如果找到目标点
			{
				flag=1;//标记已完成
				break;//退出	
			} 
		} 
		if(flag==1) break;
		head++;//head++才能对后面的点进行二次扩展 
	} 
} 
int main()
{
	cin>>r>>s;
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=s;j++)
		{
			cin>>c[i][j];
		}
	}
	p=r;q=s;//终点坐标
	head=1;tail=2;
	que[tail].x=1; que[tail].y=1; que[tail].s=0+1;
	tail++;
	f[1][1]=1;
	flag=0;
	//初始化
	bfs();
	if(flag==1) cout<<"Yes";
	else cout<<"No"; 
	return 0;
}

练习

P1443 马的遍历

题目描述

有一个 n * m 的棋盘，在某个点 (x, y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 n, m, x, y。

输出格式

一个 n * m 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 -1）。

样例 #1

样例输入 #1

1
3 3 1 1

样例输出 #1

1
2
3
0    3    2    
3    -1   1    
2    1    4

提示

数据规模与约定

对于全部的测试点，保证 1 <= x <= n <= 400，1 <= y <= m <= 400。

关于

更多练习请见: https://www.luogu.com.cn/training/463808

本文的作者是Minecraft-Sep，本文原创，禁止抄袭！