信息学奥赛一本通1359：围成面积 ← Flood fill

​【题目来源】
http://ybt.ssoier.cn:8088/problem_show.php?pid=1359

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

【数据范围】
10×10 的二维数组

【算法分析】
● 扩展边界不是 “可有可无” 的技巧，而是将 “多起点 BFS” 转化为 “单起点 BFS” 的通用方法。
● 扩展边界的本质是用 “空间换逻辑简化”。
● 扩展边界的真正价值，是应对原始边界 0 被 1 分割成多个不连通区域的通用场景 —— 通过虚拟边界的 “全 0 连通性”，把 “遍历所有物理边界点” 的复杂操作，简化为 “从虚拟起点 (0,0) 一次 BFS”，这是解决 “边界连通性” 问题的经典技巧。

【算法代码】

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int N=15;
int mp[N][N];
int dx[]= {1,0,-1,0};
int dy[]= {0,1,0,-1};
int n,ans;

void bfs(int x, int y) {
    queue<PII> q;
    mp[x][y]=7; //integer not int the graph
    q.push({x,y});
    while(!q.empty()) {
        PII t=q.front();
        q.pop();
        for(int i=0; i<4; i++) {
            int tx=t.first+dx[i];
            int ty=t.second+dy[i];
            if(tx>=0 && tx<=n+1 && ty>=0 && ty<=n+1 && mp[tx][ty]==0) {
                mp[tx][ty]=7;
                q.push({tx,ty});
            }
        }
    }
}

int main() {
    n=10;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            cin>>mp[i][j];
        }
    }

    bfs(0,0);

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(mp[i][j]==0) ans++;
        }
    }
    cout<<ans<<endl;

    return 0;
}

/*
in:
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

out:
15
*/

【参考文献】
https://blog.csdn.net/pheatonhb/article/details/136652647





 

​