连通分量

给定一个 $n \times m$ 的方格矩阵，每个方格要么是空格（用 . 表示），要么是障碍物（用 * 表示）。

如果两个空格存在公共边，则两空格视为相邻。

我们称一个不可扩展的空格集合为连通分量，如果集合中的任意两个空格都能通过相邻空格的路径连接。

这其实是一个典型的众所周知的关于连通分量（Connected Component ）的定义。

现在，我们的问题如下：

对于每个包含障碍物的单元格 $\left( {x,y} \right)$，假设它是一个空格（所有其他单元格保持不变）的前提下，请你计算包含 $\left( {x,y} \right)$ 的连通分量所包含的单元格数量。

注意，所有假设求解操作之间都是相互独立的，互不影响。

输入格式

第一行包含两个整数 $n,m$。

接下来 $n$ 行，每行包含 $m$ 个字符： . 表示空格， * 表示障碍物。

输出格式

输出一个 $n$ 行 $m$ 列的字符矩阵，其中第 $i$ 行第 $j$ 列的字符对应给定矩阵中第 $i$ 行第 $j$ 列的单元格。

如果该单元格为空格，则输出字符为 . ，如果该单元格为障碍物，则输出字符为假设该单元格为空格的前提下，包含该单元格的连通分量所包含的单元格数量对 $10$ 取模后的结果。

具体格式可参照输出样例。

数据范围

前 $5$ 个测试点满足 $1 \leq n,m \leq 10$。
所有测试点满足 $1 \leq n,m \leq 1000$。

输入样例1：

3 3
*.*
.*.
*.*

输出样例1：

3.3
.5.
3.3

输入样例2：

4 5
**..*
..***
.*.*.
*.*.*

输出样例2：

46..3
..732
.6.4.
5.4.3

解题思路

　　这题写的时候想到个最暴力的做法，就遍历每一个点，如果这个点是 * 就从这个点开始dfs，统计这个点所在连通块内的点的个数，时间复杂度为$O \left( {nm \times nm} \right)$，必然会超时。然后想了很久怎么去优化，才想到只需要一遍dfs，找到所有的连通块，再遍历每一个点，如果这个点是 * ，就看看这个位置的四个方向的格子，如果这个格子是 . 那么，表明这个点与这个格子的连通块是相连的，同时还要记得判重，这四个方向的格子可能存在多个格子属于同一个连通块的情况。即使想到想到这种做法，但代码熟练度不高，光调试都用了一个多小时，经常把变量名打错然后还发现不了。

　　本质是求将某个点的上下左右四个方向的连通块合并完后，得到的新的连通块的大小。因此首先需要找到所有连通块，找连通块的方法有dfs，bfs（Flood Fill），并查集。

　　对于有障碍物的格子，先看一下四个方向一共有几个连通块。如果四个方向都是空地，即 . ，假设这四个方向的格子用$a,b,c,d$来表示，然后看一下这四个格子分别隶属于哪个连通块，也就是每个连通块的代表元素，假设这四个方向的格子的所在连通块（并查集）的代表元素分别是${a’},{b’},{c’},{d’}$，再把属于同一个连通块的格子去掉（代表元素相同），判重后假设最终得到两个不同的连通块${a’},{b’}$，那么将这两个连通块（所有不同的连通块）与障碍物的格子连通起来，得到新的连通块的大小就是$cnt \left[ {a’} \right] + cnt \left[ {b’} \right] + 1$，$cnt$数组表示该连通块包含点的数目。因此我们还需要维护每个连通块的大小。

　　同时，由于并查集一般都是用维护一维的矩阵，因此我们需要把二维矩阵展开，变成一维，即如果某个格子的坐标为$\left( {x, y} \right)$，矩阵展开后变成$x * col + y$，其中$col$为矩阵的列数。

　　并查集，AC代码如下：

 1 #include <cstdio>
 2 #include <unordered_set>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int N = 1010, M = N * N;
 7 
 8 char g[N][N];
 9 int fa[M], cnt[M];  // 通过矩阵展开把二维坐标变一维，因此可以用一维的并查集
10 int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
11 
12 int find(int x) {
13     return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
14 }
15 
16 int main() {
17     int n, m;
18     scanf("%d %d", &n, &m);
19     for (int i = 0; i < n; i++) {
20         scanf("%s", g + i);
21     }
22     
23     for (int i = 0; i < n * m; i++) {
24         fa[i] = i;
25         cnt[i] = 1;
26     }
27     
28     // 求连通块
29     for (int i = 0; i < n; i++) {
30         for (int j = 0; j < m; j++) {
31             if (g[i][j] != '.') continue;
32             for (int k = 0; k < 4; k++) {
33                 int x = i + dx[k], y = j + dy[k];
34                 
35                 // 如果g[i][j] == '.'并且四个方向的格子也是'.'，表明这两个格子在同一个连通块
36                 if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.') {
37                     int p = find(x * m + y), q = find(i * m + j);
38                     if (p != q) {   // 两个格子还没有合并到同一个连通块
39                         cnt[q] += cnt[p];
40                         fa[p] = q;
41                     }
42                 }
43             }
44         }
45     }
46     
47     unordered_set<int> st;  // 需要把哈希表定义到循环外
48     for (int i = 0; i < n; i++) {
49         for (int j = 0; j < m; j++) {
50             if (g[i][j] == '.') {
51                 printf(".");
52             }
53             else {
54                 st.clear(); // 如果哈希表在这里定义会TLE
55                 for (int k = 0; k < 4; k++) {
56                     int x = i + dx[k], y = j + dy[k];
57                     if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.') {
58                         st.insert(find(x * m + y)); // 判重
59                     }
60                 }
61                 
62                 int ret = 1;
63                 for (auto &it : st) {
64                     ret += cnt[it];
65                 }
66                 printf("%d", ret % 10);
67             }
68         }
69         printf("\n");
70     }
71     
72     return 0;
73 }

　　Flood Fill，dfs写法，AC代码如下：

 1 #include <cstdio>
 2 #include <unordered_set>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int N = 1010, M = N * N;
 7 
 8 int n, m;
 9 char g[N][N];
10 int mp[N][N], cnt[M], sz;   // mp[i][j]表示(i, j)这个格子隶属于哪个连通块，cnt[i]表示第i个连通块的大小
11 int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
12 
13 int dfs(int x, int y) { // dfs返回当前连通块包含的点数
14     mp[x][y] = sz;
15     int cnt = 1;
16     for (int i = 0; i < 4; i++) {
17         int xx = x + dx[i], yy = y + dy[i];
18         if (xx >= 0 && xx < n && yy >= 0 && yy < m && g[xx][yy] == '.' && !mp[xx][yy]) {
19             cnt += dfs(xx, yy);
20         }
21     }
22     
23     return cnt;
24 }
25 
26 int main() {
27     scanf("%d %d", &n, &m);
28     for (int i = 0; i < n; i++) {
29         scanf("%s", g + i);
30     }
31     
32     for (int i = 0; i < n; i++) {
33         for (int j = 0; j < m; j++) {
34             if (g[i][j] == '.' && !mp[i][j]) {
35                 sz++;   // 连通块数量加1
36                 cnt[sz] = dfs(i, j);    // 得到当前连通块的大小
37             }
38         }
39     }
40     
41     unordered_set<int> st;
42     for (int i = 0; i < n; i++) {
43         for (int j = 0; j < m; j++) {
44             if (g[i][j] == '.') {
45                 printf(".");
46             }
47             else {
48                 st.clear();
49                 for (int k = 0; k < 4; k++) {
50                     int x = i + dx[k], y = j + dy[k];
51                     if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.') {
52                         st.insert(mp[x][y]);
53                     }
54                 }
55                 
56                 int ret = 1;
57                 for (auto &it : st) {
58                     ret += cnt[it];
59                 }
60                 printf("%d", ret % 10);
61             }
62         }
63         printf("\n");
64     }
65     
66     return 0;
67 }

参考资料

　　AcWing 4420. 连通分量（AcWing杯 – 周赛）：https://www.acwing.com/video/3870/

今天的文章连通分量_连通分量定义分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/55139.html

连通分量_连通分量定义