次元传送门：洛谷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; }
