3411 洪水 CodeVS原创

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

输出仅一行，为永远不会被淹没的格子的数量。

样例输入 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<iostream>
#include<cstdio>
using namespace std;
long long int a[1001][1010];
long long int b[1010][1010];
void ks(int,int);
long long m,n;
int main()
{
    long long l,r;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
     {
         for(int j=1;j<=n;j++)
          {
              scanf("%d",&a[i][j]);
          }
     }
     scanf("%d%d",&l,&r);
     ks(l,r);
     long long k=0;
     for(int i=1;i<=m;i++)
      {
          for(int j=1;j<=n;j++)
           {
               if(b[i][j]!=10)
                {
                    k++;
                }
           }
      }
      if(k==2)
       {
           cout<<0;
           return 0;
       }
      printf("%d",k-1);
      return 0;
}
void ks(int x,int y)
{
    if(x==m||y==n)return;
    int q=a[x][y];
    if(a[x-1][y]<q&&b[x-1][y]!=10)
    {
        b[x-1][y]=10;
        ks(x-1,y);
    }
    if(a[x+1][y]<q&&b[x+1][y]!=10)
    {
        b[x+1][y]=10;
        ks(x+1,y);
    }
    if(a[x][y+1]<q&&b[x][y+1]!=10)
    {
        b[x][y+1]=10;
        ks(x,y+1);
    }
    if(a[x][y-1]<q&&b[x][y-1]!=10)
    {
        b[x][y-1]=10;
        ks(x,y-1);
    }
}