codevs——3411 洪水
题解
题目描述
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<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define N 1001 using namespace std; bool vis[N][N]; int n,m,x,y,a[N][N],ans,sum; int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; int dfs(int x,int y) { for(int i=0;i<4;i++) if(vis[x+xx[i]][y+yy[i]]&&a[x][y]>=a[x+xx[i]][y+yy[i]]) { vis[x+xx[i]][y+yy[i]]=false; ans++; dfs(x+xx[i],y+yy[i]); } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]),vis[i][j]=true; scanf("%d%d",&x,&y); vis[x][y]=false; dfs(x,y); sum=n*m-1; printf("%d",sum-ans); return 0; }