欢迎光临散文网 会员登陆 & 注册

c++队列练习·图形面积

2023-08-13 09:20 作者:三无的白象牛蛙汤面  | 我要投稿

题目描述

编程计算由“*”号围成的下列图形的面积。面积计算方法是统计*号所围成的闭合曲线 中水平线和垂直线交点的数目。如下图所示,在 10*10 的二维数组中,有“*”围住了 15 个点,因此面积为 15。
 

输入

一个10*10的矩阵其中1表示*号

输出

一个数,求被星号围起来的面积

样例输入

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

样例输出

15

我的看法:洪水填充法有什么难的?!

代码:

#include<bits/stdc++.h>
using namespace std;
int screen[105][105];
typedef struct vec
{
    int i,j;
}Ract;
queue<Ract> que;
int di[]={1,0,-1,0};
int dj[]={0,-1,0,1};
void flood(int i,int j)
{
    int d;
    Ract pos{i,j};
    screen[i][j]=1;
    que.push(pos);
    while(!que.empty())
    {
        pos=que.front();
        que.pop();
        for(int d=0;d<4;d++)
        {
            int ti=di[d]+pos.i;
            int tj=dj[d]+pos.j;
            if(screen[ti][tj]==0&&ti<=10&&tj<=10&&ti>=1&&tj>=1)
            {
                screen[ti][tj]=1;
                que.push({ti,tj});
            }
        }
    }
}
int main()
{
    int i,j;
    for(int i=1;i<=10;i++)
    {
        for(int j=1;j<=10;j++)
        {
            scanf("%d",&screen[i][j]);
        }
    }
    for(int i=1;i<=10;i++)
    {
        for(int j=1;j<=10;j++)
        {
            if(i==1||j==1||i==10||j==10)
            {
                if(screen[i][j]==0)
                    flood(i,j);
            }
        }
    }
    int cnt=0;
    for(int i=1;i<=10;i++)
    {
        for(int j=1;j<=10;j++)
        {
            if(screen[i][j]==0)
            {
                cnt++;
            }
        }
    }
    printf("%d",cnt);
    return 0;
}



c++队列练习·图形面积的评论 (共 条)

分享到微博请遵守国家法律