题目描述

在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个N 行M 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。

为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。

因此，只有与湖泊毗邻的第1 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。由于第N 行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。

输入输出格式

输入格式：

 

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

 

输出格式：

 

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

 

输入输出样例

输入样例#1：

【输入样例1】2 59 1 5 4 38 7 6 1 2【输入样例2】3 68 4 5 6 4 47 3 4 3 3 33 2 2 1 1 2

输出样例#1：

【输出样例1】11【输出样例2】13

说明

【样例1 说明】

只需要在海拔为9 的那座城市中建造蓄水厂，即可满足要求。

【样例2 说明】

上图中，在3 个粗线框出的城市中建造蓄水厂，可以满足要求。以这3 个蓄水厂为源头

在干旱区中建造的输水站分别用3 种颜色标出。当然，建造方法可能不唯一。

【数据范围】

 

 

DFS+线段覆盖

注意不知道为什么需要先跑一边DFS求是否能完全覆盖

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 using namespace std; 8 const int MAXN=1001; 9 void read(int & n) 10 { 11 char c='+';int x=0;bool flag=0; 12 while(c<'0'||c>'9') 13 {c=getchar();if(c=='-')flag=1;} 14 while(c>='0'&&c<='9') 15 {x=x*10+(c-48);c=getchar();} 16 flag==1?n=-x:n=x; 17 } 18 int n,m; 19 int map[MAXN][MAXN]; 20 struct node 21 { 22 int l,r,id; 23 }xushui[MAXN]; 24 int xx[5]={-1,+1,0,0}; 25 int yy[5]={ 0,0,-1,+1}; 26 int vis[MAXN]; 27 int vis2[MAXN][MAXN]; 28 int happen=0; 29 void pdcan(int x,int y) 30 { 31 if(x==n) 32 happen++; 33 vis2[x][y]=1; 34 for(int i=0;i<4;i++) 35 { 36 int wx=x+xx[i]; 37 int wy=y+yy[i]; 38 if(vis2[wx][wy]==0&&map[wx][wy]
           
            =1&&wy>=1&&wx<=n&&wy<=m) 39 pdcan(wx,wy); 40 } 41 } 42 void dfs(int num,int x,int y) 43 { 44 if(x==n) 45 { 46 xushui[num].l=min(xushui[num].l,y); 47 xushui[num].r=max(xushui[num].r,y); 48 vis[y]=1; 49 } 50 for(int i=0;i<4;i++) 51 { 52 int wx=x+xx[i]; 53 int wy=y+yy[i]; 54 if(map[wx][wy]
            
             =1&&wy>=1&&wx<=n&&wy<=m) 55 dfs(num,wx,wy); 56 } 57 } 58 int cannot=0; 59 int comp(const node & a,const node & b) 60 { 61 if(a.l==b.l) 62 return a.r>b.r; 63 return a.l
             
              1001)continue;105 if(now+1>=xushui[i].l)106 to=max(to,xushui[i].r);107 else 108 {109 now=to;110 to=max(to,xushui[i].r);111 ans++;112 }113 }114 if(now!=m)115 printf("1\n%d",ans+1);116 else117 printf("1\n%d",ans);118 return 0;119 }