c++队列练习·图形面积
题目描述
编程计算由“*”号围成的下列图形的面积。面积计算方法是统计*号所围成的闭合曲线 中水平线和垂直线交点的数目。如下图所示,在 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;
}