【数据结构】图—图非0面积

叶茂林

发布于 2023-07-30 13:23:10

1800

发布于 2023-07-30 13:23:10

文章被收录于专栏：叶子的开发者社区

题目描述

编程计算由"1"围成的下列图形的面积。面积计算方法是统计"1"所围成的闭合曲线中"0"点的数目。如图所示，在10*10的二维数组中，"1"围住了15个点，因此面积为15。

提示：queue

输入

测试次数t

每组测试数据格式为：

数组大小m,n

一个由0和1组成的m*n的二维数组

输出

对每个二维数组，输出符号"1"围住的"0"的个数，即围成的面积。假设一定有1组成的闭合曲线，但不唯一。

输入样例1

2 10 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 5 8 0 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0

输出样例1

15 5

思路分析

我看了一下，好像有两种思路，一个是用BFS，一个是到处走。但都是把0变1实现的。我没看出来这道题和图有什么关系？

用BFS的，是在外围扩大一圈0，这样可以走进去。

我用的是到处乱走法（思路并非我首创，但名字应该是），我从四面八方开始走，只要我能到达的地方，通通由0变1，直到碰到1，即使碰到1，我也会上下左右乱窜。

之后数一下0的个数，输出即可。

AC代码

#include<iostream>
using namespace std;
const int max_len=100;
class Map{
    int m,n,area=0;
    int volume[max_len][max_len]={0};
public:
    Map(){
        cin>>m>>n;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                cin>>volume[i][j];
    }
    void ToFullPath(int x,int y){
        if(x<0||y<0||x>=m||y>=n||volume[x][y])
            return;
        volume[x][y]=1;
        ToFullPath(x,y+1);
        ToFullPath(x,y-1);
        ToFullPath(x-1,y);
        ToFullPath(x+1,y);
    }
    void AllPathCount(){
        for(int i=0;i<m;i++){
            ToFullPath(i,0);
            ToFullPath(i,n-1);
        }
        for(int i=0;i<n;i++){
            ToFullPath(0,i);
            ToFullPath(m-1,i);
        }
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(!volume[i][j])
                    area++;
        cout<<area<<endl;
    }
};
int main() {
    int t;
    cin>>t;
    while(t--){
        Map test;
        test.AllPathCount();
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-11-08，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构