在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十分特殊,刚好构成一个N 行M 列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市都有一个海拔高度。
为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施有两种,分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。
因此,只有与湖泊毗邻的第1 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差,将湖水从高处向低处输送。故一座城市能建造输水站的前提,是存在比它海拔更高且拥有公共边的相邻城市,已经建有水利设施。由于第N 行的城市靠近沙漠,是该国的干旱区,所以要求其中的每座城市都建有水利设施。那么,这个要求能否满足呢?如果能,请计算最少建造几个蓄水厂;如果不能,求干旱区中不可能建有水利设施的城市数目。
输入格式:
输入文件的每行中两个数之间用一个空格隔开。输入的第一行是两个正整数N 和M,表示矩形的规模。接下来N 行,每行M 个正整数,依次代表每座城市的海拔高度。
输出格式:
输出有两行。如果能满足要求,输出的第一行是整数1,第二行是一个整数,代表最少建造几个蓄水厂;如果不能满足要求,输出的第一行是整数0,第二行是一个整数,代表有几座干旱区中的城市不可能建有水利设施。
输入样例#1:
【输入样例1】
2 5
9 1 5 4 3
8 7 6 1 2
【输入样例2】
3 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2
输出样例#1:
【输出样例1】
1
1
【输出样例2】
1
3
【样例1 说明】
只需要在海拔为9 的那座城市中建造蓄水厂,即可满足要求。
【样例2 说明】
上图中,在3 个粗线框出的城市中建造蓄水厂,可以满足要求。以这3 个蓄水厂为源头
在干旱区中建造的输水站分别用3 种颜色标出。当然,建造方法可能不唯一。
【数据范围】
DFS+线段覆盖
注意不知道为什么需要先跑一边DFS求是否能完全覆盖
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #include<algorithm>
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]<map[x][y]&&wx>=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]<map[x][y]&&wx>=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<b.l;
64 }
65 int main()
66 {
67 freopen("flow.in","r",stdin);
68 freopen("flow.out","w",stdout);
69 read(n);read(m);
70 for(int i=1;i<=m;i++)
71 {
72 xushui[i].l=0x7ffff;
73 xushui[i].r=-1;
74 }
75 for(int i=1;i<=n;i++)
76 for(int j=1;j<=m;j++)
77 read(map[i][j]);
78 for(int i=1;i<=m;i++)
79 if(vis2[1][i]==0)
80 pdcan(1,i);
81 if(happen!=m)
82 {
83 printf("0\n%d",m-happen);
84 return 0;
85 }
86 for(int i=1;i<=m;i++)
87 {
88 xushui[i].id=i;
89 dfs(i,1,i);
90 }
91 for(int i=1;i<=m;i++)
92 if(vis[i]==0)
93 cannot++;
94 if(cannot)
95 {
96 printf("0\n%d",cannot);
97 return 0;
98 }
99 int to=0;//已经伸展到的最远长度
100 int now=0;
101 int ans=0;// 需要几个点
102 for(int i=1;i<=m;i++)
103 {
104 if(xushui[i].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 else
117 printf("1\n%d",ans);
118 return 0;
119 }