次元传送门：洛谷P1514
思路
可以证明如果有解 那么每个蓄水池可以覆盖到的干旱区必定是线段
证明：
举个栗子
8 9 8
7 9 7
6 9 6
明显到不了中间的点 如果不是连续的线段 中间肯定有一个点到不了 无解
那么我们就可以从每个开头城市进行DFS 并且同时递归计算每个点可以到达的最左边和最右边
最后进行一个线段覆盖问题解决
注意最左边是取最小值 最右边是取最大值
代码
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define maxn 505
int dx[
4]={
0,
0,
1,-
1},
dy[4]={
1,-
1,
0,
0};
int n,m,ans,sum,num;
int high[maxn][maxn],l[maxn][maxn],r[maxn][maxn];
bool vis[maxn][maxn],k;
void dfs(
int x1,
int y1)
{
vis[x1][y1]=
1;
for(
int i=
0;i<
4;i++)
//枚举方向
{
int x2=x1+
dx[i];
int y2=y1+
dy[i];
if(x2>=
1&&x2<=n&&y2>=
1&&y2<=m&&high[x2][y2]<high[x1][y1])
//判断条件
{
if(!vis[x2][y2]) dfs(x2,y2);
//如果下一个点没有被遍历过 进行遍历
l[x1][y1]=min(l[x1][y1],l[x2][y2]);
//递归时计算最右边和最左边
r[x1][y1]=
max(r[x1][y1],r[x2][y2]);
}
}
}
int main()
{
memset(l,0x3f,
sizeof(l));
//因为取最小值 所以赋值为极大值
cin>>n>>
m;
for(
int i=
1;i<=m;i++) l[n][i]=r[n][i]=i;
//初始化边界（最下面一行）
for(
int i=
1;i<=n;i++
)
for(
int j=
1;j<=m;j++) cin>>
high[i][j];
for(
int i=
1;i<=m;i++
)
{
if(vis[
1][i]==
0)
//如果这个城市没有试过且没有被其他蓄水池到达过
dfs(
1,i);
//进行搜索
}
for(
int i=
1;i<=m;i++)
//判断是否有解
if(!vis[n][i])
//如果最后一行有一个没有被到达过的点 即无解
{
num++;
//计算有几个不能到达
k=
1;
}
if(k)
//无解
{
cout<<
0<<endl<<
num;
return 0;
}
int now=
1;
//线段覆盖
while(now<=m)
//如果当前处在位置小于总长就继续
{
int maxr=
0;
//当前区间可以覆盖到的最右边
for(
int i=
1;i<=m;i++)
//枚举区间
if(l[
1][i]<=now) maxr=max(maxr,r[
1][i]);
//计算最右边
sum++;
//增加数量
now=maxr+
1;
//计算最左边
}
cout<<
1<<endl<<
sum;
}
转载于:https://www.cnblogs.com/BrokenString/p/9878921.html
