题目描述 Description

 

在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政 区划十分特殊，刚好构成一个N行M列的矩形，如上图所示，其中每个格子都代表一座城 市，每座城市都有一个海拔高度。 为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施 有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的 蓄水池中。因此，只有与湖泊毗邻的第1行的城市可以建造蓄水厂。而输水站的功能则是通 过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是 存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。 由于第N行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利 设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干 旱区中不可能建有水利设施的城市数目。

输入描述 Input Description

输入的每行中两个数之间用一个空格隔开。 输入的第一行是两个正整数N和M，表示矩形的规模。 接下来N行，每行M个正整数，依次代表每座城市的海拔高度。

输出描述 Output Description

输出有两行。如果能满足要求，输出的第一行是整数1，第二行是一个整数，代表最少 建造几个蓄水厂；如果不能满足要求，输出的第一行是整数0，第二行是一个整数，代表有 几座干旱区中的城市不可能建有水利设施。

样例输入 Sample Input

2 5

9 1 5 4 3

8 7 6 1 2

样例输出 Sample Output

1

1

数据范围及提示 Data Size & Hint

【数据范围】 本题共有10个测试数据，每个数据的范围如下表所示： 测试数据编号 能否满足要求 N M 1 不能 ≤ 10 ≤ 10 2 不能 ≤ 100 ≤ 100 3 不能 ≤ 500 ≤ 500 4 能 = 1 ≤ 10 5 能 ≤ 10 ≤ 10 6 能 ≤ 100 ≤ 20 7 能 ≤ 100 ≤ 50 8 能 ≤ 100 ≤ 100 9 能 ≤ 200 ≤ 200 10 能 ≤ 500 ≤ 500 对于所有的10个数据，每座城市的海拔高度都不超过10^6

 

样例2 说明

 

 

 

数据范围

 

数据结构分析：矩阵存储（图论）

算法：深度优先搜索

思路：

先假设第一行的所有的点都建设蓄水厂，即可求出第n行的点是否都可以被访问到。如果不行则输出此时剩余没有被访问到的点的个数。

如果可以，接下来的目的就是求最少的蓄水厂数。在已经确定最后一行都是可以访问到的情况下，可以证明，第一行访问到的最后一行的点都是连续的。

    接着可以用DFS，求出能够到达最后一行的左边界l[i]和右边界r[i]。

   最后用一次贪心就可以求出答案了。。

 

    貌似还可以用用DP求最少要用几段可以覆盖1..n。 F[i,j]表示前i段，到达j位置的最小蓄水厂数。 f[i,j]=f[i-1,st[i]-1]+1(l[i]<=j<=r[i]);  可以降维至f[j]=f[l[i]-1]+1;但是还没有写这个代码，觉得貌似有矛盾。。。

 

#include
        
         #include
         
          int a[505][505],f[505];int v[505],vv[505][505];int l[505],r[505];int n,m;void dfs(int i,int j,int k){   vv[i][j]=0;   if (i==n)   {       v[j]=1;       if(j
          
           r[k])            r[k]=j;   }   if ((a[i][j]>a[i][j-1])&&(vv[i][j-1]))        dfs(i,j-1,k);   if ((a[i][j]>a[i][j+1])&&(vv[i][j+1]))        dfs(i,j+1,k);   if ((a[i][j]>a[i+1][j])&&(vv[i+1][j]))        dfs(i+1,j,k);   if ((a[i][j]>a[i-1][j])&&(vv[i-1][j]))        dfs(i-1,j,k);}main(){    int sum=0,i,j,k;    scanf("%d%d",&n,&m);    for(i=1;i<=n;i++)       for(j=1;j<=m;j++)          scanf("%d",&a[i][j]);    for(i=1;i<=m;i++)         l[i]=m+1;        for(k=1;k<=m;k++)      if((a[1][k]>=a[1][k-1])&&(a[1][k]>=a[1][k+1]))      {          memset(vv,1,sizeof(vv));          dfs(1,k,k);      }         for(i=1;i<=m;i++)        if(!v[i])          sum++;   if(sum>0)      {       printf("0\n%d\n",sum);        return 0;     }   i=1;k=0;   while(i<=m)   {      for(j=1;j<=m;j++)         if(l[j]<=i&&r[j]>k)             k=r[j];      i=k+1;      sum++;   }    printf("1\n%d\n",sum);    return 0;}