497. 引水入城 - AcWing题库
这道题大体是说,一个 $n\times m$ 的矩阵,每个格子都有一个高度,然后行数为 $1$ 的各自都有一个蓄水池,然后,然后现在想在行数为 $n$ 的行上面建立一个输水站,而输水站的功能则是通过输水管线利用高度落差,将湖水从高处向低处输送。所以一座城市能建造输水站的前提,是存在比它海拔更高且拥有公共边的相邻城市,已经建有水利设施。
如果能,请计算最少建造几个蓄水厂;如果不能,求干旱区中不可能建有水利设施的城市数目。
思路
这道题的话,我们发现,如果蓄水池到达的区间中间有一个空白格无法到达,那么其他的也无法到达,因为都要经过一个路线。所以能到达的就会产生一个个连续区间,那么这个的话我们只需要一个贪心来做区间重复就可以了
然后我们发现,我们只需要区间的左右端点,接着我们就能想到,当前点往左走所能走到最左边的点就是左端点,走到最右边的点就是右端点。
那么如何走呢?
首先如果没有海拔条件,就只能往上下左右走,那么我们只要判断一下上下左右的方格海拔是否比当前的方格高,然后再深搜下去就可以了。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 550;
int n, m;
int h[N][N];
PII f[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void dp(int x, int y)
{
auto &p = f[x][y];
if(p.x != -1)//计算过了
return;
p.x = N;
if(x == n)//如果是最后一行
p = {y, y};//起码可以遍历到y这个点
for(int i = 0; i < 4; i ++ )
{
int tx = x + dx[i], ty = y + dy[i];
if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && h[tx][ty] < h[x][y])//没有越界
{
dp(tx, ty);
p.x = min(p.x, f[tx][ty].x);
p.y = max(p.y, f[tx][ty].y);
}
}
}
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]);
memset(f, -1, sizeof f);
for(int i = 1; i <= m; i ++ )
dp(1, i);
int cnt = 0;
for(int i = 1; i <= m; i ++ )
if(f[n][i].x == -1)
cnt ++ ;
if(cnt > 0)
{
cout << 0 << '\n' << cnt;
return 0;
}
else
{
vector<PII> e;
for(int i = 1; i <= m; i ++ )
e.push_back(f[1][i]);
sort(e.begin(), e.end());
int res = 0;
for(int i = 0, start = 1; i < m;)//start表示下一个需要覆盖的位置
{
int maxr = 0;//最多能遍历到的右端点
while(i < m && e[i].x <= start)
{
maxr = max(maxr, e[i].y);
i ++ ;
}
res ++ ;
if(maxr >= m)
break;
start = maxr + 1;
}
cout << 1 << endl << res;
}
return 0;
}