【题目描述】
编程计算由“*”号围成的下列图形的面积。面积计算方法是统计*号所围成的闭合曲线中水平线和垂直线交点的数目。如下图所示,在10×10的二维数组中,有“*”围住了15个点,因此面积为15。
【输入】
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【输出样例】
15
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 11
#define MOD 123
#define E 1e-6
using namespace std;
int a[N][N];
int vis[N][N];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int cnt=0;
struct node{
int x;
int y;
}q[200];
void bfs(int x0,int y0)
{
a[x0][y0]=1;
vis[x0][y0]=1;
int head=1,tail=1;
q[tail].x=x0;
q[tail].y=y0;
tail++;
while(head<tail)
{
int x=q[head].x;
int y=q[head].y;
for(int i=0;i<4;i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(1<=nx&&nx<=10&&1<=ny&&ny<=10&&a[nx][ny]==0&&vis[nx][ny]==0)
{
vis[nx][ny]=1;
a[nx][ny]=1;
q[tail].x=nx;
q[tail].y=ny;
tail++;
}
}
head++;
}
}
void bfs_cnt(int x0,int y0)
{
vis[x0][y0]=1;
cnt++;
int head=1,tail=1;
q[tail].x=x0;
q[tail].y=y0;
tail++;
while(head<tail)
{
int x=q[head].x;
int y=q[head].y;
for(int i=0;i<4;i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(1<=nx&&nx<=10&&1<=ny&&ny<=10&&a[nx][ny]==0&&vis[nx][ny]==0)
{
vis[nx][ny]=1;
q[tail].x=nx;
q[tail].y=ny;
tail++;
cnt++;
}
}
head++;
}
}
int main()
{
for(int i=1;i<=10;i++)
for(int j=1;j<=10;j++)
cin>>a[i][j];
for(int j=1;j<=10;j++)
if(a[1][j]==0)
bfs(1,j);
for(int j=1;j<=10;j++)
if(a[10][j]==0)
bfs(10,j);
for(int i=1;i<=10;i++)
if(a[1][i]==0)
bfs(1,i);
for(int i=1;i<=10;i++)
if(a[10][i]==0)
bfs(10,i);
for(int i=1;i<=10;i++)
for(int j=1;j<=10;j++)
if(a[i][j]==0&&vis[i][j]==0)
bfs_cnt(i,j);
cout<<cnt<<endl;
return 0;
}
信息学奥赛一本通T1359:队列 围成面积 归属于 队列,更多同类题解源程序见:队列 和 围成面积
0 篇文章
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!