BFS专题2 矩阵中的块

原创 于 2023-07-31 22:57:30 发布 · 粉丝可见 · 99 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132032158

题目：

样例：

6 7 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 0 1 1 1 1 0 0 0

4

思路：

BFS宽度搜索，这里我们每碰到一个 ‘1’ 块,就遍历标记好哪些 ‘1’ 与这块相连，然后看我们碰到多少次就是多少个块，代码详解如下：

#include <iostream>
#include <queue>
#define endl '\n'
#define x first
#define y second
#define mk make_pair
using namespace std;
 
using PII = pair<int,int>;
 
const int N = 500;
 
int n,m;	// 矩阵大小
 
int ans;	// 最终答案块
 
int g[N][N];	// 矩阵数组
 
bool vis[N][N];	// 标记块 数组
 
// 坐标移动操作
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
 
// 坐标走动条件
bool isRun(int bx,int by)
{
	return (bx >= 0 && bx < n && by >= 0 && by < m && g[bx][by] && !vis[bx][by]);
}
 
void BFS(int x,int y)
{
	queue<PII>q;
	q.push(mk(x,y));
	while(q.size())
	{
		PII t = q.front();
		q.pop();
 
		// 标记当前走动的坐标
		vis[t.x][t.y] = true;
		
		// 开始走动
		for(int i = 0;i < 4;++i)
		{
			int bx = t.x + dx[i];
			int by = t.y + dy[i];
			if(isRun(bx,by))
			{
				q.push(mk(bx,by));
			}
		}
	}
	return ;
}
 
int main()
{
	cin >> n >> m;
	for(int i = 0;i < n;++i)
	{
		for(int j = 0;j < m;++j)
		{
			cin >> g[i][j];
		}
	}
 
	for(int i = 0;i < n;++i)
	{
		for(int j = 0;j < m;++j)
		{
			if(!vis[i][j] && g[i][j])
			{
				ans++;
				BFS(i,j);
			}
		}
	}
 
	cout << ans << endl;
	return 0;
}

最后提交：