【题目来源】
【题目描述】
oibh 被突来的洪水淹没了，还好 oibh 总部有在某些重要的地方起一些围墙。用 * 号表示，而一个四面被围墙围住的区域洪水是进不去的。
oibh 总部内部也有许多重要区域，每个重要区域在图中用一个 0 表示。
现在给出 oibh 的围墙建设图，问有多少个没被洪水淹到的重要区域。
【输入格式】
第一行为两个正整数 x，y。
接下来 x 行，每行 y 个字符，由 * 和 0 组成，表示 oibh 总部的建设图。
【输出格式】
输出没被水淹没的 oibh 总部的 0 的数量。
【输入样例一】
4 5
00000
00*00
0*0*0
00*00
【输出样例一】
1
【输入样例二】
5 5
*****
*0*0*
**0**
*0*0*
*****
【输出样例二】
5
【数据范围】
对于100%的数据，1≤x,y≤500。
【算法分析】
● 本题与“信息学奥赛一本通1359：围成面积”的算法思想一致，都是“扩展边界”，详见：
● 扩展边界思想
（1）扩展边界不是 “可有可无” 的技巧，而是将 “多起点 BFS” 转化为 “单起点 BFS” 的通用方法。
（2）扩展边界的本质是用 “空间换逻辑简化”。
（3）扩展边界的真正价值，是应对原始边界 0 被 1 分割成多个不连通区域的通用场景 —— 通过虚拟边界的 “全 0 连通性”，把 “遍历所有物理边界点” 的复杂操作，简化为 “从虚拟起点 (0,0) 一次 BFS”，这是解决 “边界连通性” 问题的经典技巧。
● cin 会读入二维 char 数组每行后的换行符吗？
默认情况下，cin 读取 char 类型时，会自动跳过换行符、空格等空白字符，不会把它们存入 char 数组。
【算法代码一：dfs + char 数组】
全局二维 char 数组未显示初始化时，其元素的值是随机 ASCII 字符（不是 '0'），所以需要利用命令 memset(mp,'0',sizeof mp); 显示初始化。
#include<bits/stdc++.h>
using namespace std;const int N=505;
char mp[N][N];
int dx[]= {1,0,-1,0};
int dy[]= {0,1,0,-1};
int n,m,ans;void dfs(int x,int y) {mp[x][y]='*';for(int i=0; i<4; i++) {int tx=x+dx[i];int ty=y+dy[i];if(tx>=0 && tx<=n+1 && ty>=0 && ty<=m+1 && mp[tx][ty]=='0') {dfs(tx,ty);}}
}int main() {memset(mp,'0',sizeof mp); //very importantcin>>n>>m;for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {cin>>mp[i][j];}}dfs(0,0);for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {if(mp[i][j]=='0') ans++;}}cout<<ans<<endl;return 0;
}/*
in:
5 5
*****
*0*0*
**0**
*0*0*
*****out:
5
*/
【算法代码二：bfs + pair + char 数组】
全局二维 char 数组未显示初始化时，其元素的值是随机 ASCII 字符（不是 '0'），所以需要利用命令 memset(mp,'0',sizeof mp); 显示初始化。
#include<bits/stdc++.h>
using namespace std;typedef pair<int,int> PII;
const int N=505;
char mp[N][N];
int dx[]= {1,0,-1,0};
int dy[]= {0,1,0,-1};
int n,m,ans;void bfs(int x,int y) {queue<PII> q;mp[x][y]='*';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<=m+1 && mp[tx][ty]=='0') {mp[tx][ty]='*';q.push({tx,ty});}}}
}int main() {memset(mp,'0',sizeof mp); //very importantcin>>n>>m;for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {cin>>mp[i][j];}}bfs(0,0);for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {if(mp[i][j]=='0') ans++;}}cout<<ans<<endl;return 0;
}/*
in:
5 5
*****
*0*0*
**0**
*0*0*
*****out:
5
*/【算法代码三：dfs + int 数组】
#include<bits/stdc++.h>
using namespace std;const int N=505;
int mp[N][N];
int dx[]= {1,0,-1,0};
int dy[]= {0,1,0,-1};
int n,m,ans;
char ch;void dfs(int x,int y) {mp[x][y]=1;for(int i=0; i<4; i++) {int tx=x+dx[i];int ty=y+dy[i];if(tx>=0 && tx<=n+1 && ty>=0 && ty<=m+1 && mp[tx][ty]==0) {dfs(tx,ty);}}
}int main() {cin>>n>>m;for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {cin>>ch;if(ch=='*') mp[i][j]=1;else mp[i][j]=0;}}dfs(0,0);for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {if(mp[i][j]==0) ans++;}}cout<<ans<<endl;return 0;
}/*
in:
5 5
*****
*0*0*
**0**
*0*0*
*****out:
5
*/【算法代码四：bfs + pair + int 数组】
#include<bits/stdc++.h>
using namespace std;typedef pair<int,int> PII;
const int N=505;
int mp[N][N];
int dx[]= {1,0,-1,0};
int dy[]= {0,1,0,-1};
int n,m,ans;
char ch;void bfs(int x, int y) {queue<PII> q;mp[x][y]=1;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<=m+1 && mp[tx][ty]==0) {mp[tx][ty]=1;q.push({tx,ty});}}}
}int main() {cin>>n>>m;for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {cin>>ch;if(ch=='*') mp[i][j]=1;else mp[i][j]=0;}}bfs(0,0);for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {if(mp[i][j]==0) ans++;}}cout<<ans<<endl;return 0;
}/*
in:
5 5
*****
*0*0*
**0**
*0*0*
*****out:
5
*/
【参考文献】