经典的flood fill 问题 bfs

#include<iostream>
#include<queue>
using namespace std;
typedef pair<int,int> PAII;
const int N=1010;
char ch[N][N];
bool st[N][N];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m;
void bfs(int x,int y)
{
	queue<PAII> q;
	q.push({x,y});
	st[x][y]=true;
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		int a=t.first,b=t.second;
		for(int i=0;i<4;i++)
		{
			int xx=a+dx[i],yy=b+dy[i];
			if(xx<0||yy<0||xx>=n||yy>=m) continue;
			if(ch[xx][yy]=='#'&&!st[xx][yy])
			{
				q.push({xx,yy});
				st[xx][yy]=true;
			}
		}
	}
	
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			cin>>ch[i][j];
	int sum=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		{
			if(!st[i][j]&&ch[i][j]=='#')
			{
				bfs(i,j);
				sum++;
			}
		}
	cout<<sum;
	return 0;
}

和油田一模一样

using namespace std;
#define N 500
char a[N][N];
int n,m,cnt;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
void dfs(int x,int y ){
if(x<0||x>=n||y<0||y>=m||a[x][y]=='.')return ;
a[x][y]='.';//搜过的点 标记为.,或者重新开个vis[N][N]也ok
//搜索可到达点
for(int i=0;i<4;i++){
int tx=x+dx[i];
int ty=y+dy[i];
dfs(tx,ty);
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>a[i][j];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]=='#'){
dfs(i,j);
cnt++;
}
}
}
cout<<cnt<<endl;
return 0;
}

这道题我使用的是DFS的算法

#include <bits/stdc++.h>

using namespace std;
const int N = 100 + 10;

bool vis[N][N] = {false};
char mp[N][N];
int dx[4] = {0, 0, -1, 1};//定义x方向的移动
int dy[4] = {-1, 1, 0, 0};//定义y方向的移动
int r, c; //草丛的宽和长
int ans = 0; //记录草丛数量
int fg = 0; //记录岛屿

void dfs(int x, int y) {
	if (vis[x][y] == true) {
		return;
	}//每次调用都检查一下vis是否被访问
	vis[x][y] = true;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i]; //向四个方向扩散
		int ny = y + dy[i];
		if (vis[nx][ny] == false && mp[nx][ny] == '#') {
			dfs(nx, ny);//如果四个方向存在连接的,那么就进行标记
		}
	}
}

int main() {
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> mp[i][j];
		}
	}
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++ ) {
			if (mp[i][j] == '#' && vis[i][j] == false) {
				dfs(i, j); //遍历每一块土地
				ans++;
			}
		}
	}
	cout << ans;
	return 0;
}