【9802】闭合曲线面积

Time Limit: 3 second
Memory Limit: 2 MB

【问题描述】

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

【输入格式】

共有m行,每行n列。“*”号用1表示。其余位置用0表示，两数之间用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

【输出样例】

【题解】

把1看成围墙，我们是想进入围墙的人，但是怎么也进不了，于是我们就在围墙的周围乱走，把能不进围墙就走到的地方走个遍。然而她就是这么无懈可击，我也真是醉了。然后删掉围墙。剩下的就是被围住的东西了，看得到，但是永远得不到，因为它们被围起来了。从每个角落都进行一次广搜，找连通块，找到了置为false就可以了。

【代码】

#include <cstdio>

const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};

int a[15][15],dl[9000][2],ans = 0;
bool bo[15][15];

void input_data()
{
    for (int i = 1;i <= 10;i++)
        for (int j = 1; j<= 10;j++) //输入数据
            scanf("%d",&a[i][j]);
    for (int i = 1;i <= 10;i++) //所有的格子一开始都没有被走过。
        for (int j = 1;j <= 10;j++)
            bo[i][j] = true;
}

void bfs(int x,int y) //从x,y开始找连通块
{
    int head = 1,tail = 1;
    bo[x][y] =false; //标记已经走过
    dl[head][0] = x; //把这个点入队列，表示可以从这个点向外扩展
    dl[1][1] = y;
    while (head <= tail)
        {
            int xx = dl[head][0],yy = dl[head][1]; //把头结点中存的数据取出来
            head++;
            for (int i = 0;i <= 3;i++) //往4个方向扩展
                {
                    int tx = xx + dx[i];
                    int ty = yy + dy[i];
                    if (tx < 1) continue; //如果越界 或者撞上墙就跳过
                    if (tx > 10) continue;
                    if (ty < 1) continue;
                    if (ty > 10) continue;
                    if (a[tx][ty] == 1) continue;
                    if (bo[tx][ty]) //如果这个位置可以走 那么就入队列 表示可以从扩展出的结点继续扩展
                        {
                            dl[++tail][0] = tx;
                            dl[tail][1] = ty;
                            bo[tx][ty] = false;
                        }
                }
        }
}

void get_ans()
{
    for (int i = 1;i <= 10;i++) //从左边界突破
        if ( a[i][1]!=1 && bo[i][1]) //如果这个位置不是墙，且是10*10的边界，那么就从这个地方突破
            bfs(i,1);
    for (int i = 1;i <= 10;i++) //从上边界突破
        if (a[1][i] != 1 && bo[1][i])
            bfs(1,i);
    for (int i = 1;i <= 10;i++) //从下边界突破
        if (a[10][i] !=1 && bo[10][i])
            bfs(10,i);
    for (int i = 1;i <= 10;i++) //从右边界突破
        if (a[i][10] !=1 && bo[i][10])
            bfs(i,10);
    for (int i = 1;i <= 10;i++) //如果是墙则也不能突破
        for (int j = 1; j <= 10;j++)
            if (a[i][j] == 1)
                bo[i][j] = false;
    for (int i = 1;i <= 10;i++) //遇到了墙里面的东西就递增答案。
        for (int j = 1;j <= 10;j++)
            if (bo[i][j])
                ans++;
}

void output_ans()
{
    printf("%d
",ans);
}

int main()
{
    input_data();
    get_ans();
    output_ans();
    return 0;
}