用 DFS 在 2D 地图上找连通分量的问题
例 4 蓝桥杯 —— 全球变暖展开目录
题目大意是有一张 NxN 像素的照片,图片中”#” 代表陆地,”.” 代表海洋。” 上下左右”4 连通连成一片的陆地组成一座岛屿。如下图题目里的照片中,有两座岛屿,分别用红框标记出来:
然后题目说由于全球变暖,海平面上升,预计岛屿边缘一个像素范围内的陆地都会被淹没。所谓岛屿边缘像素就是与海洋相邻的像素,也就是上下左右有海洋的像素
比如在上图中,红色的陆地都会被淹没。题目最后要求你计算预计有多少岛屿被全部淹没。在上图中,左上的岛屿被完全淹没了
这道题的基本思路比较直观,就是用 DFS 找出来所有 #号组成的连通分量。同时计算每一个连通分量包含几个 #号,以及包含几个与。点相邻的 #号。其中找连通分量这一步是一个很常见的套路,很多题目都会用到。直接看完整的代码:
- #include <iostream>
- #include <String>
- using namespace std;
- int n,m;
- int mark[1000][1000];
- string s[1000];
- int cnt[1000000],flood[1000000];
- int ans = 0;
- int dx[4] = {-1,1,0,0};
- int dy[4] = {0,0,-1,1};
- void dfs(int x,int y,int m){
- mark[x][y] = m;
- cnt[m]++;
- bool flooded = false;
- for(int d = 0;d < 4;d++)
- {
- int nx = x + dx[d];
- int ny = y + dy[d];
- if(s[nx][ny] == '.')
- flooded = true;
- if(s[nx][ny] == '#' && mark[nx][ny] == 0)
- dfs(nx,ny,m);
- }
- if(flooded)
- flood[m]++;
- }
- int main()
- {
- cin >> n;
- for(int i = 0;i < n;i++)
- cin >> s[i];
- for(int i = 0;i < n;i++)
- for(int j = 0;j < n;j++)
- mark[i][j] = 0;
- m = 0;
- ans = 0;
- for(int i = 0;i < n;i++)
- {
- for(int j = 0;j < n;j++)
- {
- if(s[i][j] == '#' && mark[i][j] == 0)
- {
- m++;
- cnt[m] = flood[m] = 0;
- dfs(i,j,m);
- if(cnt[m] == flood[m])
- ans++;
- }
- }
- }
- cout << ans << endl;
- return 0;
- }
我们要找到连通分量,具体来说是要计算出这么一些数据数来。首先是有多少个连通分量,保存在变量 m 里。其次我们要给每个陆地像素打上标记,标记出来它属于哪一个连通分量。这个数据我们用二维数组 mark [][] 表示。marki=k 表示 i 行 j 列这个陆地像素属于第 k 个连通分量
cnt [i] 记录第 i 个连通分量包含几个陆地像素;flood [i] 记录第 i 个连通分量包含几个与海相邻的陆地像素。显然 cnt [i]==flood [i] 意味着第 i 座岛屿被全部淹没了
主函数 main 除去输入的部分,也就是 37~50 行在用 2 重循环先行后列访问每一个像素 (i, j),如果是陆地,并且 marki 值是 0,说明还没有被 DFS 处理过,属于一座新的岛屿;于是就岛屿数 m 加一,从 (i, j) 开始深搜出整个岛屿。DFS 过程中会顺便计算出 cnt [m] 和 flood [m],如果二者相等就答案 ans 加一
主要看一下第 11~26 行的 dfs 函数。参数 xym 表示现在搜索到 (x, y) 这个像素,并且 (x, y) 以及后续搜到的与 (x, y) 连通的像素都属于第 m 个连通分量
对于 (x, y) 我们要搜索它的 4 个邻居像素 (x+1, y), (x-1, y), (x, y-1), (x, y+1)。第 15~18 行的代码,d=0,1,2,3 分别代表了上下左右 4 个方向,该方向上的邻居是就是 (nx, ny)
一般我们求出 (nx, ny) 之后需要判断这个点在不在合法范围里,比如坐标出现负数就说明不在范围里。不过在这道题中,数据保证图片边缘都是海,所以我们不用担心出界的问题
第 19 行的意思是,如果 (x, y) 的邻居 (nx, ny) 是海,那么 (x, y) 会被淹没,我们就把标记 flooded 置为 true。如果 (nx, ny) 是尚未被标记陆地,就继续从 (nx, ny) 开始递归搜索下去。第 24 行,当我们把 (x, y) 的上下左右 4 个邻居都递归处理完,将要退出 dfs (x, y, m) 的时候,判断 (x, y) 是不是被标记淹没,如果是就令 flood [m] 加 1
由于我们不会遍历 mark 值不为 0 的像素,保证了每个像素只会被 dfs 处理一次。而每次 dfs 执行只会向 4 个邻居扩展,所以整个程序的时间复杂度是 $O (N^2)$
例 5 题目链接:hihoCoder1310展开目录
这道题的背景与上一道题很类似,也是 NxM 的照片中有用 #表示的岛屿和用。表示的海洋。不过问题是 (1) 有几座岛屿;(2) 有几座面积不同的岛屿;(3) 有几座形状不同的岛屿
其中第一问和第二问,通过学习上一道题目,我们应该已经会解决了。问题在于第三问,求形状不同的岛屿,注意这里两座岛屿形状相同当且仅当能通过平移使它们重合,旋转和翻转 (对称) 都是不行的。所以样例中一横排 4 个 #和一竖列 4 个 #不算形状相同
我们可以用下面的算法判断两个岛屿是否形状相同。首先我们为每一个陆地像素编号,具体来说 i 行 j 列 (从 0 开始计数) 的像素 (i, j) 的编号是 i*m+j。然后对于每一个岛屿,我们用一个 vector 记录它包含的所有陆地像素的编号,并将编号从小到大排序
最后我们判断两个岛屿形状是否相同时,只需判断它们是不是满足 vector 中的对应编号的差是一个定值。例如上图样例中,(1, 2, 3, 4) 与 (14, 15, 16, 17) 对于编号的差 14-1=15-2=16-3=17-4 都是 13,所以两座岛屿形状相同。而 (1, 2, 3, 4) 和 (12, 19, 26, 33) 形状就不同
- #include <iostream>
- #include <cstring>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int n,m,k,ka,ks;
- char g[1000][1000];
- bool vis[100][100];
- int dx[4] = {-1,1,0,0};
- int dy[4] = {0,0,-1,1};
- vector<int> islands[10000];
- int hash_func(int x,int y)
- {
- return x * m + y;
- }
- int inb(int x,int y)
- {
- return x >= 0 && x < n && y >= 0 && y < m;
- }
- void dfs(int x,int y,vector<int>& island){
- vis[x][y] = true;
- island.push_back(hash_func(x,y));
- for(int d = 0;d < 4;d++)
- {
- int nx = x + dx[d];
- int ny = y + dy[d];
- if(inb(nx,ny) && !vis[nx][ny] && g[nx][ny] == '#')
- dfs(nx,ny,island);
- }
- }
- bool shape_similar(vector<int> &islandi,vector<int>& islandj)
- {
- if(islandi.size() != islandj.size())
- return false;
- int d = islandi[0] - islandj[0];
- for(int i = 1;i < islandi.size();i++)
- {
- if(islandi[i] - islandj[i] != d)
- return false;
- }
- return true;
- }
- int main()
- {
- cin >> n >> m;
- for(int i = 0;i < n;i++)
- cin >> g[i];
- memset(vis,false,sizeof(vis));
- k = 0;
- for(int i = 0;i < n;i++)
- {
- for(int j = 0;j < m;j++)
- {
- if(g[i][j] == '#' && !vis[i][j])
- {
- islands[k].clear();
- dfs(i,j,islands[k]);
- sort(islands[k].begin(),islands[k].end());
- k++;
- }
- }
- }
- ka = ks = 0;
- for(int i = 0;i < k;i++)
- {
- bool fa = false,fs = false;
- for(int j = 0;j < i;j++)
- {
- if(islands[i].size() == islands[j].size())
- fa = true;
- if(shape_similar(islands[i],islands[j]))
- fs = true;
- }
- if(!fa)
- ka++;
- if(!fs)
- ks++;
- }
- cout << k << ' ' << ka << ' ' << ks << endl;
- return 0;
- }
char g [][] 保存了整个照片。bool vis [][] 的作用与上一题的 mark [][] 类似,不过这里是 bool 类型,true 代表对应的像素已经处理过了,false 代表还没处理过。vector<int> islands [10000] 保存了每座岛屿的陆地标号序列,具体来说 islands [i] 这个 vector 里是第 i 座岛屿的陆地编号序列。islands 最后用来比较面积和形状
第 12-15 行这个 hash_func 函数其实就是在算我们之前提到的编号。第 16~19 行 inb 函数用来判断 (x, y) 这个位置在不在边界里。第 20~30 行是求连通分量的 dfs 函数,我们可以比较一下这个 dfs 和上一道题的 dfs 函数,可以发现基本上是相同的。稍微有点不同的是第 22 行,我们要把 (x, y) 的编号保存在 island 这个 vector 里
第 31~42 行 shape_similar 函数,顾名思义就是在判断两个岛屿形状是不是相同。具体算法我们之前也提到过了,就是计算对应的差值 d 是不是一个固定的数值。如果所有的差都一样,那么形状就是相同的
主函数 50-62 行是在扫描每个像素,试图找到一个未标记的陆地开始深搜出整个连通分量。上一道题的主函数里也是基本一样的代码。最后 64-78 行是在两两比较岛屿的面积和形状,不再赘述