MENU

搜索(4)

June 26, 2018 • Read: 220 • 算法

用DFS在2D地图上找连通分量的问题

例4 蓝桥杯——全球变暖

image

题目大意是有一张NxN像素的照片,图片中”#”代表陆地,”.”代表海洋。”上下左右”4连通连成一片的陆地组成一座岛屿。如下图题目里的照片中,有两座岛屿,分别用红框标记出来:

image

然后题目说由于全球变暖,海平面上升,预计岛屿边缘一个像素范围内的陆地都会被淹没。所谓岛屿边缘像素就是与海洋相邻的像素,也就是上下左右有海洋的像素

image

比如在上图中,红色的陆地都会被淹没。题目最后要求你计算预计有多少岛屿被全部淹没。在上图中,左上的岛屿被完全淹没了

这道题的基本思路比较直观,就是用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]加一

由于我们不会遍历mark值不为0的像素,保证了每个像素只会被dfs处理一次。而每次dfs执行只会向4个邻居扩展,所以整个程序的时间复杂度是O(N^2)

例4 题目链接:hihoCoder1310

image

这道题的背景与上一道题很类似,也是NxM的照片中有用#表示的岛屿和用.表示的海洋。不过问题是(1)有几座岛屿;(2)有几座面积不同的岛屿;(3)有几座形状不同的岛屿

其中第一问和第二问,通过学习上一道题目,我们应该已经会解决了。问题在于第三问,求形状不同的岛屿,注意这里两座岛屿形状相同当且仅当能通过平移使它们重合,旋转和翻转(对称)都是不行的。所以样例中一横排4个#和一竖列4个#不算形状相同

我们可以用下面的算法判断两个岛屿是否形状相同。首先我们为每一个陆地像素编号,具体来说i行j列(从0开始计数)的像素(i, j)的编号是i*m+j。然后对于每一个岛屿,我们用一个vector记录它包含的所有陆地像素的编号,并将编号从小到大排序

image

最后我们判断两个岛屿形状是否相同时,只需判断它们是不是满足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行是在两两比较岛屿的面积和形状,不再赘述

最后编辑于: October 19, 2018
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment