AcWing 4420. 连通分量
原题链接
中等
作者:
.Oranges
,
2022-05-14 20:18:30
,
所有人可见
,
阅读 436
- 首先将二维数组的每个元素通过[行 * 列元素个数 + 列]转换为一维数组并查集
- 对输入的二维字符串,对所有能够相通的 ‘ . ‘ 进行并查集的合并
- 输出:当前位置元素为 ‘ * ‘,假设当前位置为空格,则连通分量元素的个数为 (1(当前位置) + 四个方向上由并查集合并的不同的连通块的元素总个数) % 10
#include <cstdio>
#include <iostream>
#include <unordered_map>
using namespace std;
typedef pair<int, int> PII;
const int N = 1005;
int n, m;
char ch[N][N];
int cont[N * N]; // 将二维数组的每个元素转换为一维并查集
int dir[N * N]; // 并查集的集合元素个数
bool st[N][N];
unordered_map<int, int> heap;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int find(int x) {
if (cont[x] == x) return x;
return cont[x] = find(cont[x]);
}
void dfs(int x, int y) {
st[x][y] = true;
for (int i = 0; i < 4; i ++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (ch[nx][ny] == '*' || st[nx][ny]) continue;
int l = find(x * m + y);
int r = find(nx * m + ny);
dir[l] += dir[r];
cont[r] = cont[l];
dfs(nx, ny);
}
}
int cnt(int x, int y) {
int s = 1;
heap.clear();
for (int i = 0; i < 4; i ++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (ch[nx][ny] == '*') continue;
int idx = find(nx * m + ny);
if (heap.count(idx)) continue;
s += dir[idx];
heap[idx] ++;
}
return s % 10;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i ++) scanf("%s", ch[i]);
// 并查集初始化
for (int i = 0; i < n * m; i ++)
cont[i] = i, dir[i] = 1;
// 将相同的元素合并
for (int i = 0; i < n; i ++) {
for (int j = 0; j < m; j ++) {
if (ch[i][j] == '*') continue;
dfs(i, j);
}
}
// 输出
for (int i = 0; i < n; i ++) {
for (int j = 0; j < m; j ++) {
if (ch[i][j] == '.') {
printf(".");
continue;
}
// (1(当前位置) + 四个方向上的不同的连通块的元素总数量) % 10
printf("%d", cnt(i, j));
}
printf("\n");
}
return 0;
}