题目描述

编程计算由‘ * ’号围成的下列图形的面积。面积的计算方法是统计 *号所围成的闭合曲线中水平线和垂直线交点的数目。

如图所示，在10*10的二维数组中，有*围住了15个点，因此面积为15。

思路

从四个角进行bfs,开始时ans值为100，读入是遇到1ans–，bfs时没覆盖一个点ans–
O(100)

#include 
#include 
#include 
using namespace std;
int n=10,ans=100,a[11][11];
int dx[5]={0,1,0,-1,0};
int dy[5]={0,0,1,0,-1};
int bfs(int x,int y)
{
    queue tx;
    queue ty;
    tx.push(x); ty.push(y);
    ans--;
    a[x][y]=1;
    while (!tx.empty())
    {
        int xx=tx.front(),yy=ty.front();
        tx.pop(),ty.pop();
        for (int i=1;i<=4;i++)
            if (dx[i]+xx>=1&&dx[i]+xx<=n&&dy[i]+yy>=1&&dy[i]+yy<=n&&a[dx[i]+xx][dy[i]+yy]==0)
            {
                a[dx[i]+xx][dy[i]+yy]=1;
                ans--;
                tx.push(dx[i]+xx);
                ty.push(dy[i]+yy);
            }
    }
}
int main()
{
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            if (a[i][j]==1) ans--;
        }
    if (a[1][1]==0)
        bfs(1,1);
    if (a[1][n]==0)
        bfs(1,n);
    if (a[n][1]==0)
        bfs(n,1);
    if (a[n][n]==0)
        bfs(n,n);
    printf("%d\n",ans);
}