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