引水入城

题目

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

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

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

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例

2 5
9 1 5 4 3
8 7 6 1 2

输出样例

1
1

思路

第一步

深搜判断是否有解

将第一行都建上蓄水厂然后进行深搜判断最后一行是否都可以遍历到(宽搜也可做)

第二步

通过对每一个都建一次蓄水厂得到l[i], r[i]; 表示如果在i这个点建蓄水厂的话可以是最后一行的l[i]~r[i]都能够得到水

第三步

进行dp将问题转化为区间覆盖问题选择最少的区间使其覆盖整个区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int n, m, h[505][505];
int vis[505][505];
int r[505], l[505];
int dp[505];
void dfs(int x,int y)
{
if (vis[x][y]) return ;
vis[x][y] = 1;
if (x + 1 <= n && h[x][y] > h[x + 1][y]) dfs(x + 1, y);
if (x - 1 >= 1 && h[x][y] > h[x - 1][y]) dfs(x - 1, y);
if (y + 1 <= m && h[x][y] > h[x][y + 1]) dfs(x, y + 1);
if (y - 1 >= 1 && h[x][y] > h[x][y - 1]) dfs(x, y - 1);
return ;
}
void dfs1(int k, int x, int y, int Time)
{
if (vis[x][y]) return ;
if (x == 1)
{
if (Time == 1) r[y] = k;
if (Time == 2) l[y] = k;
}
if (x + 1 <= n && h[x][y] < h[x + 1][y]) dfs1(k, x + 1, y, Time);
if (x - 1 >= 1 && h[x][y] < h[x - 1][y]) dfs1(k, x - 1, y, Time);
if (y + 1 <= m && h[x][y] < h[x][y + 1]) dfs1(k, x, y + 1, Time);
if (y - 1 >= 1 && h[x][y] < h[x][y - 1]) dfs1(k, x, y - 1, Time);
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
scanf("%d",&h[i][j]);
for (int i=1; i<=m; i++)
dfs(1, i);
int ret = 0;
for (int i=1; i<=m; i++)
if (!vis[n][i])
ret ++;
if (ret)
{
printf("0\n%d\n", ret);
return 0;
}
memset(vis, 0, sizeof(vis));
for (int i=1; i<=m; i++)
{
dfs1(i, n, i, 1);
}
for (int i=m; i>=1; i--)
{
dfs1(i, n, i, 2);
}
memset(dp, 127/3, sizeof(dp));
dp[0] = 0;
for (int i=1; i<=m; i++)
for (int j=1; j<=m; j++)
if (l[j] <= i && r[j] >= i)
{
dp[i] = min(dp[l[j] - 1] + 1, dp[i]);
}
printf("1\n%d\n", dp[m]);
return 0;
}