這道題就統計有多少個連通塊就行了

這時候我們又需要把二維轉成一維了，也就是把每一個格子都給一個編號

當我們合并連通塊的時候，其實是只需要四個方向的

因為我們是從上往下遍歷的，我們遍歷到某個位置的時候，它已經和上面部分合并完了，我們只需要考慮右邊和下邊就行了

就像如圖

最后我們的答案就是有多少個連通塊，也就是多少個是W并且fa[i]=i

#include <iostream>
using namespace std;
int n, m;
const int N = 110;
char a[N][N];
int fa[N * N];
int dx[] = { 0,1,1,1 };
int dy[] = { 1,0,-1,1 };
int find(int x)
{return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void un(int x, int y)
{int px = find(x);int py = find(y);fa[px] = py;
}
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 * m; i++){fa[i] = i;}for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (a[i][j] == 'W'){for (int k = 0; k < 4; k++){int p = i * m + j;int x = i + dx[k], y = j + dy[k];if (x<0 || y<0 || x>=n || y>=m || a[x][y]=='.') continue;int cur = x * m + y;un(p, cur);}}}}int cnt = 0;for (int i = 0; i < n * m; i++){int x = i / m, y = i % m;if (a[x][y] == '.') continue;if (fa[i] == i) cnt++;}cout << cnt << endl;return 0;
}