[算法提高] DFS 深度优先搜索数岛屿连通块面积

今天药忘吃喽~ 2022-03-06 09:06 221阅读 0赞

**\[问题背景\]**

假设'\#'是陆地，'.'是海洋。

![2019031816165091.png][]

我们从图中把左、上、右、下四个方向相邻的'\#'连起来作为一个连通块，也就是一个“岛屿”，每个岛屿的面积就是'\#'的个数。

如图：

![20190318161848715.png][]

图中有三个连通块，按自左向右再自上而下的顺序，三个连通块的面积依次是4、2、1.

输出这些连通块的面积。

\[测试样例1\]

\#\#.\#.  
\#..\#.  
\#...\#

\[输出样例1\]

4 2 1

\[测试样例2\]

\#\#.\#..  
\#..\#..  
\#...\#.  
\#\#\#...  
\#....\#

\[输出样例2\]

8 2 1 1

\[测试样例3\]

\#\#\#..\#  
\#.\#...  
\#\#\#...  
......  
\#\#\#.\#\#  
\#.\#.\#.

\[输出样例3\]

8 1 5 3

**\[思路分析\]**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N3b3JkdHJhdmVsbGVy_size_16_color_FFFFFF_t_70][]

以左边的连通块为例，应能实现这样的递归访问，每次递归时都将面积+1

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N3b3JkdHJhdmVsbGVy_size_16_color_FFFFFF_t_70 1][]

我们对二维数组中的元素进行遍历循环，遇到\#就开始深搜，搜完一整个连通块后返回整个大循环，继续遍历后面的元素。

**\[代码求解\]**

以下是针对测试样例3编写的代码。

#define N 6
    #define M 6
    #include <iostream>
    #include <vector>
    using namespace std;
    
    void dfs(int, int); // 声明深搜dfs函数 
    
    // 在main()之外声明的都是全局变量，main()后面的函数也可以使用这些全局变量 
    char c[N][M]; // 记录#.图 
    vector<int>area; // 记录各个连通块的面积 
    int sum = 0; // 置面积初值为0 
    int vis[N][M] = {0}; //记录每个元素是否被访问过，初值0表示没有访问过 
    
    int main(){
        //int N, M; //N行M列 
        //cin >> N >> M;
        //因为传长度为变量的二维数组给函数的问题本人还没有解决，所以很抱歉只能用宏定义的方法做 
        
        //记录#.图 
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                cin >> c[i][j];
            }
        }
    	
    	//遍历#.图中的元素 
        for (int i = 0; i < N; i++){
            for (int j = 0; j < M; j++){
            	//如果这个元素[没有被访问过 && 是'#'] 那么对它深搜 
                if (vis[i][j] == 0 && c[i][j] == '#') dfs(i,j);
                // 如果这个元素对应的连通块面积不是0，那么记入area中 
    			// 对于. 这个元素也会生成为0的sum 
                if (sum!= 0) area.push_back(sum);
                sum = 0; // 重置sum 
            }
        }
        //迭代器遍历area，输出结果 
        for (auto it = area.begin(); it != area.end(); it++){
            cout << *(it) << " ";
        }
        return 0;
    }
    
    void dfs(int i, int j){
    	//深搜到达c[i][j]时标记其已被访问 
        vis[i][j] = 1;
        //深搜到达新的'#'时面积加1 
        sum++;
        //以下两行注释代码是输出样例中不需要的，它们只是帮你调试程序看过程变化用 
        //cout << "i=" << i << "j=" << j << endl;
        //cout << "sum=" << sum << endl << endl; 
        
        //left
        //向左，不能碰到边界，应该是没有被访问过的，应该是"#"号 
        if(j > 0 && vis[i][j-1] == 0 && c[i][j-1] == '#'){
            dfs(i, j-1);
            //递进到c[i][j-1]进行深搜 
        }
        //up
        //以下照此类推，注意各个下标不要写错 
        if(i > 0 && vis[i-1][j] == 0 && c[i-1][j] == '#'){
            dfs(i-1, j);
        }
        //right 
        if(j < N-1 && vis[i][j+1] == 0 && c[i][j+1] == '#'){
            dfs(i, j+1);
        }
        //down 
        if(i < N-1 && vis[i+1][j] == 0 && c[i+1][j] == '#'){
            dfs(i+1, j);
        }else{
            return; //返回，对某个元素展开的深搜结束 
        }
    }

输出结果：

8 1 5 3

代码简洁版：

#define N 6
    #define M 6
    #include <iostream>
    #include <vector>
    using namespace std;
    
    void dfs(int, int); 
    
    char c[N][M];
    vector<int>area;
    int sum = 0; 
    int vis[N][M] = {0};
    
    int main(){
    	for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                cin >> c[i][j];
            }
        }
        
        for (int i = 0; i < N; i++){
            for (int j = 0; j < M; j++){
                if (vis[i][j] == 0 && c[i][j] == '#') dfs(i,j);
                if (sum!= 0) area.push_back(sum);
                sum = 0; 
            }
        }
        
        for (auto it = area.begin(); it != area.end(); it++){
            cout << *(it) << " ";
        }
        
        return 0;
    }
    
    void dfs(int i, int j){
        vis[i][j] = 1;
        sum++;
        if(j > 0 && vis[i][j-1] == 0 && c[i][j-1] == '#'){
            dfs(i, j-1);
        }
        if(i > 0 && vis[i-1][j] == 0 && c[i-1][j] == '#'){
            dfs(i-1, j);
        }
        if(j < N-1 && vis[i][j+1] == 0 && c[i][j+1] == '#'){
            dfs(i, j+1);
        }
        if(i < N-1 && vis[i+1][j] == 0 && c[i+1][j] == '#'){
            dfs(i+1, j);
        }else{
            return;
        }
    }

很抱歉因为我个人的水平原因暂没有能写出由用户指定N行M列的代码，以后解决了会在这里补充，也希望得到高手的批评指正，非常感谢！

**\[方法总结\]**

深搜一般要通过递归实现，本题的深搜思路大致是：

1.遍历图中的每个元素

2.对未访问过的目标元素进行深搜

3.深搜时注意考虑图的边界和历史访问性的记录

4.对深搜产生的目标数据的处理

**最值得注意的两点是：**

**1.图的边界**

**2.元素是否被访问过，这一信息的记录和处理**

**\[拓展提高\]**

我认为人不应该仅仅满足于闭门造轮，也要出门看一看别人造的轮子是不是更好更快更漂亮。

所以我学习了这位博主的文章，虽然代码行数差不多：

小白成长日记（15）--岛屿面积问题（算法设计--dfs深度优先搜索） - rangkuimei0880的博客 - CSDN博客 [https://blog.csdn.net/rangkuimei0880/article/details/78609941][https_blog.csdn.net_rangkuimei0880_article_details_78609941]

\[测试样例\]

1 2 1 0 0 0 0 0 2 3   
3 0 2 0 1 2 1 0 1 2   
4 0 1 0 1 2 3 2 0 1   
3 2 0 0 0 1 2 4 0 0   
0 0 0 0 0 0 1 5 3 0   
0 1 2 1 0 1 5 4 3 0   
0 1 2 3 1 3 6 2 1 0   
0 0 3 4 8 9 7 5 0 0   
0 0 0 3 7 8 6 0 1 2   
0 0 0 0 0 0 0 0 1 0

\[输出样例\]

9 5 38 3

\[代码拓展\]

#define N 10
    #define M 10
    #include <iostream>
    #include <vector>
    using namespace std;
    
    int dfs(int, int); 
    
    int c[N][M];
    vector<int>area;
    int vis[N][M] = {0};
    
    int main(){
    	for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                cin >> c[i][j];
            }
        }
        
        for (int i = 0; i < N; i++){
            for (int j = 0; j < M; j++){
                if (vis[i][j] == 0 && c[i][j] != 0) {
                	int temp = dfs(i,j);
                	if(temp!=0) area.push_back(temp);
    			}
            }
        }
        
        for (auto it = area.begin(); it != area.end(); it++){
            cout << *(it) << " ";
        }
        
        return 0;
    }
    
    int dfs(int i, int j){
        int sum = 0;
        if (j >= 0 && i >= 0 && j < N && i < N) { //注意这里的=号能否取到
        	if (vis[i][j] == 0 && c[i][j] != 0 ) {
        		vis[i][j] = 1;
    			sum = 1;
        		sum += dfs(i,j-1);
        		sum += dfs(i-1,j);
        		sum += dfs(i,j+1);
        		sum += dfs(i+1,j);
    		}
    		return sum; 
    	}else{
    		return 0;
    	}
    }

也是一种可行的解法。将dfs定义为int更为直接，返回值就是答案。

将dfs定义为void ，则需要更多地考虑全局变量的操作，但也能适应多任务场景，比如不但要数面积，还要统计岛屿数量和形状等。

我想了一下，开大数组可以由用户指定N和M，不过总归还不是那么完美，毕竟大数组也有个上限，就贴在这里吧。

#define MaxN 1000
    #define MaxM 1000 
    #include <iostream>
    #include <vector>
    using namespace std;
    
    void dfs(int, int, int, int); 
    
    char c[MaxN][MaxM];
    vector<int>area;
    int sum = 0; 
    int vis[MaxN][MaxM] = {0};
    
    int main(){
    	int N, M;
    	cin >> N >> M;
    	for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                cin >> c[i][j];
            }
        }
        
        for (int i = 0; i < N; i++){
            for (int j = 0; j < M; j++){
                if (vis[i][j] == 0 && c[i][j] == '#') dfs(i,j,N,M);
                if (sum!= 0) area.push_back(sum);
                sum = 0; 
            }
        }
        
        for (auto it = area.begin(); it != area.end(); it++){
            cout << *(it) << " ";
        }
        
        return 0;
    }
    
    void dfs(int i, int j, int N, int M){
        vis[i][j] = 1;
        sum++;
        if(j > 0 && vis[i][j-1] == 0 && c[i][j-1] == '#'){
            dfs(i, j-1, N, M);
        }
        if(i > 0 && vis[i-1][j] == 0 && c[i-1][j] == '#'){
            dfs(i-1, j, N, M);
        }
        if(j < N-1 && vis[i][j+1] == 0 && c[i][j+1] == '#'){
            dfs(i, j+1, N, M);
        }
        if(i < N-1 && vis[i+1][j] == 0 && c[i+1][j] == '#'){
            dfs(i+1, j, N, M);
        }else{
            return;
        }
    }

[2019031816165091.png]: /images/20220303/7d82585c9b9a4574a7eb4c8622813881.png
[20190318161848715.png]: /images/20220303/7e4544e831a74bf3916fe9562384b6c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N3b3JkdHJhdmVsbGVy_size_16_color_FFFFFF_t_70]: /images/20220303/ec244330c0944c378610734e43e75c19.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N3b3JkdHJhdmVsbGVy_size_16_color_FFFFFF_t_70 1]: /images/20220303/12bc8193e599409f844a446d27203d93.png
[https_blog.csdn.net_rangkuimei0880_article_details_78609941]: https://blog.csdn.net/rangkuimei0880/article/details/78609941