首页 > 代码库 > codevs3411 洪水
codevs3411 洪水
题目描述 Description
小浣熊松松和朋友到野外露营，没想到遇上了π年一次的大洪水，好在松松是一只爱观察的小浣熊，他发现露营地的地形和洪水有如下性质：
①露营地可以被看做是一个N*M的矩形方阵，其中左上角坐标为(1,1)，右下角坐标为(n,m)，每个格子(i,j)都有一个高度h(i,j)。
②洪水送(r,c)开始，如果一个格子被洪水淹没，那这个格子四周比它低（或相同）的格子也会被淹没。
现在松松想请你帮忙算算，有多少个格子不会被淹没，便于他和朋友逃脱。
【原有误数据已删除】
输入描述 Input Description
第一行包含两个整数n，m，表示矩形方阵右下角坐标。
以下n行，每行m个数，第i行第j个数表示格子(i,j)的高度。
最后一行包含两个整数r，c，表示最初被洪水淹没的格子。
输出描述 Output Description
输出仅一行，为永远不会被淹没的格子的数量。
样例输入 Sample Input
3 3
1 2 3
2 3 4
3 4 5
2 2
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
对于90%的数据，保证随机生成。
对于100%的数据，1<=N,M<=1000。
代码：
#include<cstdio>#include<iostream>#include<cstring>#include<string>using namespace std;const int maxn = 2005;int j[maxn][maxn],room[maxn][maxn];long long int total = 0,m,n;struct pos{ int x; int y;};pos q[4000000];pos dir[4];int bfs(int y,int x){ int h = 0,t = 0; q[0].y = y; q[0].x = x; int tx,ty; while(h <= t){ int r3 = 0; for(r3 = 0;r3 < 4;r3++){ x = q[h].x; y = q[h].y; tx = dir[r3].x; ty = dir[r3].y; if(y + ty >= 0 && y + ty < n && x + tx >= 0 && x + tx < m && room[y + ty][x + tx] && j[y + ty][x + tx]){ t++; q[t].y = y + ty; q[t].x = x + tx; j[y + ty][x + tx] = 0; total--; } } h++ ; }}int main(){ cin>>n>>m; dir[0].x = -1;dir[0].y = 0; dir[1].x = +1;dir[1].y = 0; dir[2].x = 0;dir[2].y = -1; dir[3].x = 0;dir[3].y = +1; char cmd; int r1 = 0,r2 = 0,temp = -1; for(r1 = 0;r1 < n;r1++){ for(r2 = 0;r2 < m;r2++){ cin>>cmd; if(cmd == ‘.‘) { j[r1][r2] = 1; room[r1][r2] = 1; total++; }else if(cmd == ‘#‘){ j[r1][r2] = 1; room[r1][r2] = 0; } } } r1 = r2 =0; for(r1 = 0;r1 < n;r1++){ for(r2 = 0;r2 < m;r2++){ if(room[r1][r2] && j[r1][r2]){ j[r1][r2] = 0; bfs(r1,r2); } } } cout<<total; return 0;}
codevs3411 洪水
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。