3411 洪水

2018-06-17 22:57:44来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

3411 洪水

 

CodeVS原创

 时间限制: 1 s
 空间限制: 64000 KB
 题目等级 : 青铜 Bronze
 
 
题目描述 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

输出仅一行,为永远不会被淹没的格子的‘’

 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 int a[1010][1010];
 5 int x,y;
 6 int xx[5]={-1,+1,0,0};
 7 int yy[5]={0,0,-1,+1};
 8 int h;
 9 int n,m;
10 int tot;
11 int vis[1010][1010];
12 int p,q;
13 void dfs(int i,int j)
14 {
15     if(i<1||j<1||i>n||j>m)
16     return;
17 
18     for(int k=0;k<4;k++)
19     {
20         h=a[i][j];
21          p=i+xx[k];
22          q=j+yy[k];
23         if(vis[p][q]==0&&a[p][q]<=h&&p>=1&&p<=n&&q>=1&&q<=m)
24         {
25             vis[p][q]=1;
26             tot--;
27             dfs(p,q);
28             //vis[p][q]=0;
29             //tot++;
30         }
31         else
32         continue;
33     }
34 }
35 int main()
36 {
37     cin>>n>>m;
38     for(int i=1;i<=n;i++)
39     {
40         for(int j=1;j<=n;j++)
41         {
42             cin>>a[i][j];
43         }
44     }
45     tot=n*m-1;
46     cin>>x>>y;
47     vis[x][y]=1;
48     dfs(x,y);
49     if(tot==-1)
50     cout<<0;
51     else
52     cout<<tot;
53     return 0;
54 }

 

 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:在Linux上部署Qt及Qwt

下一篇:读书笔记 effective c++ Item 39 明智而谨慎的使用private继承