可用DFS,BFS,并查集。在这里使用DFS,将所以为W的点记录下来,然后遍历这些点,在遍历某一个点的时候使用深度优先遍历将其相邻的所以池塘全部标记下来,这样在遍历W的时候可以将其跳过。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000+10;
char ch[maxn][maxn];
int cnt = 0;
int n, m;
pair<int, int> need[maxn];
bool vis[maxn][maxn];
int mv[8][2] {
{0,-1},
{0,1},
{-1,0},
{1,0},
{-1,-1},
{-1,1},
{1,-1},
{1,1}
};
void dfs(int x, int y) {
vis[x][y] = true;
//进行上下左右的移动
for (int i=0;i<8;i++) {
int next_x = x+mv[i][0];
int next_y = y+mv[i][1];
if (next_x<=0||next_y<=0||next_x>n||next_y>m||vis[next_x][next_y]) continue;
if (ch[next_x][next_y]=='W') {
dfs(next_x, next_y);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
cin>>ch[i][j];
if (ch[i][j]=='W') {
//记录所以积水的方块,到后面会进行遍历
need[cnt++] = {i,j};
}
}
}
int ans = 0;
//遍历所以积水的方块,如果已经被遍历过了会直接跳过
for (int i=0;i<cnt;i++) {
if (!vis[need[i].first][need[i].second]) {
dfs(need[i].first, need[i].second);
ans++;
}
}
cout<<ans;
return 0;
}

京公网安备 11010502036488号