AHU-61 Lake Counting (并查集）

简单并查集

Code

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 10000 + 10;
const int dx[] = {
   1, -1, 0, 0, 1, -1, 1, -1};
const int dy[] = {
   0, 0, 1, -1, 1, -1, -1, 1};
int node[MAXN], pre[MAXN];int find(int x) {return pre[x] == x ? x : pre[x] = find(pre[x]);
}void join(int x, int y) {int xx = find(x);int yy = find(y);if (xx != yy) {pre[yy] = xx;}
}int main() {int n, m, z;while(~scanf("%d%d", &n, &m)) {getchar();char ch;for (int i = 0; i < n; ++i) {for (int j = 0; j <= m; ++j) { //j多循环一次读换行scanf("%c", &ch);z = i * m + j;if (ch == '.') node[z] = 0;else if (ch == 'W') node[z] = 1;pre[z] = z;}}for (int i = 0; i < n*m; ++i) {if (node[i] == 0) continue;int x = i / m, y = i % m;for (int j = 0; j < 8; ++j) {int nx = x + dx[j], ny = y + dy[j];if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;int nz = nx * m + ny;if (node[nz] == 1)join(i, nz);}}set<int> root;for (int i = 0; i < n*m; ++i) {if (node[i] == 0) continue;int nroot = find(i);root.insert(nroot);}printf("%d\n", root.size());}return 0;
}