有两种做法。
Code1: 并查集
每个W
与相邻的八个W
构成同一个集合,将它们集合划分后寻找祖先结点个数就是所有连通块的个数。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
int fa[N * N];
int n, m;
char g[N][N];
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int addr(int x, int y){
return x * (m + 1) + y;
}
int find(int x){
return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
}
void Union(int x, int y){
x = find(x), y = find(y);
if(x != y) fa[x] = y;
}
bool check(int x, int y){
return x >= 1 && x <= n && y >= 1 && y <= m;
}
int main(){
ios :: sync_with_stdio(false);
cin >> n >> m;
for(int i = 1;i <= n * (m + 1) + m;i ++) fa[i] = i;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
cin >> g[i][j];
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
if(g[i][j] == 'W'){
int a = addr(i, j);
for(int k = 0;k < 8;k ++){
int nex = i + dx[k], ney = j + dy[k];
if(check(nex, ney) && g[nex][ney] == 'W'){
int b = addr(nex, ney);
Union(a, b);
}
}
}
int ans = 0;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
if(g[i][j] == 'W' && find(addr(i, j)) == addr(i, j)) //祖先结点
ans ++;
cout << ans << endl;
return 0;
}
Code2: flood_fill泛洪
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1010;
char g[N][N];
bool st[N][N];
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int n, m;
queue<PII> q;
bool check(int x, int y){
return x >= 1 && x <= n && y >= 1 && y <= m && !st[x][y] && g[x][y] == 'W';
}
void flood_fill(int sx, int sy){
q.push({sx, sy});
st[sx][sy] = true;
while(q.size()){
PII tot = q.front();
q.pop();
for(int i = 0;i < 8;i ++){ //流向八个方向有水的地方
int nex = tot.x + dx[i], ney = tot.y + dy[i];
if(check(nex, ney))
q.push({nex, ney}), st[nex][ney] = true;
}
}
}
int main(){
ios :: sync_with_stdio(false);
cin >> n >> m;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
cin >> g[i][j];
int ans = 0;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++){
if(check(i, j)){ //其实只为了用!st[x][y] && g[x][y] == 'W'这两个条件
ans ++; //每次check(i, j)后就说明找到了一个新洼地
flood_fill(i, j);
}
}
cout << ans << endl;
return 0;
}