意大利之家设计网站,wordpress显示所有文章,徐州建设工程招投标官方网站,钦州浦北网站建设拯救oibh总部
题目背景
oibh 总部突然被水淹没了#xff01;现在需要你的救援……
题目描述
oibh 被突来的洪水淹没了#xff0c;还好 oibh 总部有在某些重要的地方起一些围墙。用 * 号表示#xff0c;而一个四面被围墙围住的区域洪水是进不去的。
oibh 总部内部也有许…拯救oibh总部
题目背景
oibh 总部突然被水淹没了现在需要你的救援……
题目描述
oibh 被突来的洪水淹没了还好 oibh 总部有在某些重要的地方起一些围墙。用 * 号表示而一个四面被围墙围住的区域洪水是进不去的。
oibh 总部内部也有许多重要区域每个重要区域在图中用一个 0 表示。
现在给出 oibh 的围墙建设图问有多少个没被洪水淹到的重要区域。
输入格式
第一行为两个正整数 x , y x,y x,y。
接下来 x x x 行每行 y y y 个整数由 * 和 0 组成表示 oibh 总部的建设图。
输出格式
输出没被水淹没的 oibh 总部的 0 的数量。
样例 #1
样例输入 #1
4 5
00000
00*00
0*0*0
00*00样例输出 #1
1样例 #2
样例输入 #2
5 5
*****
*0*0*
**0**
*0*0*
*****样例输出 #2
5提示
对于 100 % 100\% 100% 的数据 1 ≤ x , y ≤ 500 1 \le x,y \le 500 1≤x,y≤500。
#includeiostream
using namespace std;
int n,m,s0;
int kx[5]{1,-1,0,0};
int ky[5]{0,0,1,-1};
int a[501][501];void search(int x,int y){a[x][y]2;//先标记被淹没了 for(int i0;i4;i){//向四个方向搜索 int x0xkx[i];int y0yky[i];if(x00x0ny00y0ma[x0][y0]0)search(x0,y0);}//如果新的数在整个数组范围内并且不是障碍(能走),那么就搜索从这个格子能走到其他哪些格子
}int main(){cinnm;char e;for(int i1;in;i){//输入 for(int j1;jm;j){cine;if(e*)a[i][j]1;//如果是障碍就输入1 else a[i][j]0;//可以过就是0 }}for(int i1;in;i){//搜索第一列和最后一列的格子 if(a[i][1]0)search(i,1);//如果有能过的就搜索 if(a[i][m]0)search(i,m);}for(int i1;im;i){//搜索第一行和最后一行的格子 if(a[1][i]0)search(1,i);if(a[n][i]0)search(n,i);}for(int i1;in;i){//最后搜索没有被淹的格子 for(int j1;jm;j){if(a[i][j]0)s;}}coutsendl;//输出 return 0;
}整体思路 这个思路比较清晰。 首先搜索周围的区域把这些区域内所有的被淹没的统统标记出来 然后遍历剩下的区域把没有被淹没的区域统计出来。 算法的思想是利用深搜算法思想。上面代码中那个search函数实现了这个算法思想。
