广度优先搜索（广搜）（c++）

广搜和深搜的用途差不多，基本上都是做，不过各有优缺点。广搜（)：对于深搜（)：对于。

mmz1207

1470人浏览 · 2025-02-08 15:03:01

mmz1207 · 2025-02-08 15:03:01 发布

简介

用途

广搜和深搜的用途差不多，基本上都是做地图中的搜索，不过各有优缺点。

广搜（BFS)：对于解决最短或最少问题特别有效

深搜（DFS)：对于解决遍历和求所有问题有效

数据结构栈

广度优先搜索使用队列来实现

1、把根节点放到队列的末尾。

2、每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。

3、找到所要找的元素时结束程序。

4、如果遍历整个树还没有找到，结束程序。

题目

接下来，直接进入练习！

快乐的马里奥

题目描述

马里奥是一个快乐的油漆工人，这天他接到了一个油漆任务，要求马里奥把一个 n 行 m 列的矩阵每一格都用油漆标记一个数字，标记的顺序按照广度优先搜索的方式进行，也就是他会按照如下方式标记：
1 、首先标记第 1 行第 1 列的单元格，标记数字为 1 ；
2 、然后标记当前单元格上下左右四个方向所有能标记的单元格，且：
① 标记顺序按照：右、下、左、上的优先级；
② 不能标记到矩阵外，且标记过的数字不能重复标记；
3 、当本单元格标记结束，寻找比本单元格中数字大 1 的单元格，标记那个单元格的上下左右四个方向，也是按照步骤 2 所示的要求进行标记。
依次类推，直到所有单元格都被标记。
比如：如果有一个3 * 3 的矩阵如下，那么首先标记 1,1 单元格，并按照上面步骤 2 的要求标记其四周能够标记的单元格，标记结果如下：

接下来，标记比 1,1 格大 1 的数字的四周的单元格，也就是标记值为 2 的单元格四周的单元格，标记结果如下：

接下来标记值为 3 的单元格四周的单元格，标记结果如下：

接下来标记值为 4 的单元格四周的单元格，标记结果如下：

接下来标记值为 5 的单元格四周的单元格，标记结果如下：

接下来标记值为 6 的单元格四周的单元格，但这个数字四周的单元格已经被标记，因此继续标记值为7四周的单元格，标记结果如下：

此时，发现标记结束，得到如上图所示的标记结果。

输入格式

两个整数 n 和 m ， n 和 m 都是 3~100 之间的整数。

输出格式

输出 n 行 m 列的标记后的矩阵，输出每个数后空一格。

样例

样例输入
3 3

样例输出
1 2 4

3 5 7

6 8 9

#include <bits/stdc++.h>

using namespace std;
int a[110][110];
int n,m;
struct point
{
	int x,y,v;
	point(){};
	point(int a,int b,int c)
	{
		x = a;
		y = b;
		v = c;
	}
};
point que[10010];
int head = 0;
int tail = 0;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int main()
{
	cin>>n>>m;
	int cnt = 1;
	a[1][1] = 1;
	que[++tail] = {1,1,1};
	while(head<tail)
	{
		head++;
		for(int i = 0;i<4;i++)
		{
			int tx = que[head].x+dx[i];
			int ty = que[head].y+dy[i];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]==0)
			{
				cnt++;
				a[tx][ty] = cnt;
				que[++tail] = {tx,ty,cnt};
			}
		}
	}
	
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=m;j++)
		{
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
	
	return 0;
}

泉水

题目描述

Leyni是一个地址调查员，有一天在他调查的地方突然出现个泉眼。由于当地的地势不均匀，有高有低，他觉得如果这个泉眼不断的向外溶出水来，这意味着这里在不久的将来将会一个小湖。水往低处流，凡是比泉眼地势低或者等于的地方都会被水淹没，地势高的地方水不会越过。而且又因为泉水比较弱，当所有地势低的地方被淹没后，水位将不会上涨，一直定在跟泉眼一样的水位上。
由于Leyni已经调查过当地很久了，所以他手中有这里地势的详细数据。所有的地图都是一个矩形，并按照坐标系分成了一个个小方格，Leyni知道每个方格的具体高度。我们假定当水留到地图边界时，不会留出地图外，现在他想通过这些数据分析出，将来这里将会出现一个多大面积的湖。

输入格式

有若干组数据，每组数据的第一行有四个整数n,m,p1,p2(0<=1000)，n和m表示当前地图的长和宽，p1和p2表示当前地图的泉眼位置，即第p1行第p2列，随后的n行中，每行有m个数据。表示这每一个对应坐标的高度。

输出格式

输出对应地图中会有多少个格子被水充满。

样例

样例输入
3 5 2 3

3 4 1 5 1

2 3 3 4 7

4 1 4 1 1

样例输出
6

#include <bits/stdc++.h>

using namespace std;
int a[1010][1010];
int b[1010][1010];
int n,m,sx,sy;
struct point
{
	int x,y;
	point(){};
	point(int a,int b)
	{
		x = a;
		y = b;
	}
};
point que[1000010];
int head = 0;
int tail = 0;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int main()
{
	cin>>n>>m>>sx>>sy;
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	
	int cnt = 1;
	b[sx][sy] = 1;
	que[++tail] = {sx,sy};
	int hi = a[sx][sy];
	while(head<tail)
	{
		head++;
		for(int i = 0;i<4;i++)
		{
			int tx = que[head].x+dx[i];
			int ty = que[head].y+dy[i];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]<=hi&&b[tx][ty]==0)
			{
				cnt++;
				b[tx][ty] = 1;
				que[++tail] = {tx,ty};
			}
		}
	}
	
	cout<<cnt;
	
	return 0;
}

迷宫出口

题目描述

一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，0和1，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为1)，则看成无法办到。

输入格式

第1行是一个正整数n (1 ≤ n ≤ 100)，表示迷宫的规模是n * n的。接下来是一个n * n的矩阵，矩阵中的元素为0或者1。再接下来一行是4个整数ha la hb lb，描述A处在第ha行第la列，B处在第hb行第lb列。

输出格式

能办到则输出“YES”，否则输出“NO”。

样例

样例输入
3

0 1 1

0 0 1

1 0 0

1 1 3 3

样例输出

YES

#include <bits/stdc++.h>

using namespace std;
int a[110][110];
int n,sx,sy,ex,ey;
struct point
{
	int x,y;
	point(){};
	point(int a,int b)
	{
		x = a;
		y = b;
	}
};
point que[1000010];
int head = 0;
int tail = 0;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int main()
{
	cin>>n;
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	}
	cin>>sx>>sy>>ex>>ey;
	if(a[sx][sy]==0||a[ex][ey]==0)
	{
		cout<<"NO";
		return 0;
	}
	que[++tail] = {sx,sy};
	while(head<tail)
	{
		head++;
		for(int i = 0;i<4;i++)
		{
			int tx = que[head].x+dx[i];
			int ty = que[head].y+dy[i];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&a[tx][ty]==0)
			{
				if(tx==ex&&ty==ey)
				{
					cout<<"YES";
					return 0;
				}
				que[++tail] = {tx,ty};
			}
		}
	}
	
	cout<<"NO";
	
	return 0;
}

数池塘（四方向）

题目描述

农夫约翰的农场可以表示成N*M（1≤N≤100≤M≤100）个方格组成的矩形。由于近日的降雨，在约翰农场上的不同地方形成了池塘。每一个方格或者有积水（'W'）或者没有积水（'.'）。农夫约翰打算数出他的农场上共形成了多少池塘。一个池塘是一系列相连的有积水的方格，每一个方格周围的四个方格都被认为是与这个方格相连的。现给出约翰农场的图样，要求输出农场上的池塘数。

输入格式

第1行：由空格隔开的两个整数：N和M
第2..N+1行：每行M个字符代表约翰农场的一排方格的状态。每个字符或者是'W'或者是'.'，字符之间没有空格。

输出格式

输出只有1行，输出约翰农场上的池塘数

样例

样例输入

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

样例输出
13

（注：样例输入中，因字符大小有差异，所以看起来不像矩形）

#include <bits/stdc++.h>
using namespace std;
struct point
{
	int x,y;
	point(){};
	point(int a,int b)
	{
		x = a;
		y = b;
	}
};
point que[1000010];
int head = 0;
int tail = 0;
char a[110][110];
int n,m;
int cnt;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int main()
{
	cin>>n>>m;
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	
	
	for(int iii = 1;iii<=n;iii++)
	{
		for(int jjj = 1;jjj<=m;jjj++)
		{
			tail = 0;
			head = 0;
			que[++tail] = {iii,jjj};
			if(a[iii][jjj]=='W')
			{
				cnt++;
				while(head<tail)
				{
					head++;
					for(int i = 0;i<4;i++)
					{
						int tx = que[head].x+dx[i];
						int ty = que[head].y+dy[i];
						if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]=='W')
						{
							que[++tail] = {tx,ty};
							a[tx][ty] = '.';
						}
					}
				}
			}
		}
	}
	
	cout<<cnt;
	
	return 0;
}