用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行是在两两比较岛屿的面积和形状，不再赘述
