QAQ 首先是第一问 这个很简单，我们只需要将上面的一排全部弄上机器，然后跑BFS，只要可以拓展出下面全部的点，就可以成功了。 再来看第二问 如果有水源可以到沙漠，那么可以到沙漠一定是连续的，我们去求每个可以到的沙漠最左和最右，最少有几个区间就可以覆盖所有沙漠，即为答案 问题转化为求区间的完全覆盖问题 方法如下： 例题1 描述：给定一个长度为m的区间，再给出n条线段的起点和终点（注意这里是闭区间），求最少使用多少条线段可以将整个区间完全覆盖 样例： 区间长度8，可选的覆盖线段[2,6],[1,4],[3,6],[3,7],[6,8],[2,4],[3,5] 解题过程: 1将每一个区间按照左端点递增顺序排列，拍完序后为[1,4]，[2,4]，[2,6]，[3,5]，[3,6]，[3,7]，[6,8] 2设置一个变量表示已经覆盖到的区域。再剩下的线段中找出所有左端点小于等于当前已经覆盖到的区域的右端点的线段中，右端点最大的线段在加入，直到已经覆盖全部的区域 3过程: 假设第一步加入[1,4]，那么下一步能够选择的有[2,6]，[3,5]，[3,6]，[3,7]，由于7最大，所以下一步选择[3,7]，最后一步只能选择[6,8]，这个时候刚好达到了8退出，所选区间为3 4贪心证明: 需要最少的线段进行覆盖，那么选取的线段必然要尽量长，而已经覆盖到的区域之前的地方已经无所谓了，（可以理解成所有的可以覆盖的左端点都是已经覆盖到的地方），那么真正能够使得线段更成的是右端点，左端点没有太大的意义，所以选择右端点来覆盖
#include <cstdio> #include <stdlib.h> #include <iostream> #include <cstring> #include <cmath> #include <queue> #include <algorithm> using namespace std; int high[501][501]; int n,m; struct tw{ int x,y; }; queue <tw> dl; struct we{ int l,r; }a[9999]; int cnt; bool map[501][501]; bool cmp(const we&a,const we&b) { if(a.l<b.l||a.l==b.r&&a.r<b.r)return 1; return 0; } int BFS() { int tot=0; for(int i=1;i<=m;i++) { tw d; d.x=1,d.y=i; map[1][i]=1; dl.push(d); } while(!dl.empty()) { tw p=dl.front(); dl.pop(); if(p.x==n) tot++; if(p.x-1>=1) if(high[p.x][p.y]>high[p.x-1][p.y]) if(!map[p.x-1][p.y]) { map[p.x-1][p.y]=1; tw opt; opt.x=p.x-1; opt.y=p.y; dl.push(opt); } if(p.y-1>=1) if(high[p.x][p.y]>high[p.x][p.y-1]) if(!map[p.x][p.y-1]) { map[p.x][p.y-1]=1; tw opt; opt.x=p.x; opt.y=p.y-1; dl.push(opt); } if(p.x+1<=n) if(high[p.x][p.y]>high[p.x+1][p.y]) if(!map[p.x+1][p.y]) { map[p.x+1][p.y]=1; tw opt; opt.x=p.x+1; opt.y=p.y; dl.push(opt); } if(p.y+1<=m) if(high[p.x][p.y]>high[p.x][p.y+1]) if(!map[p.x][p.y+1]) { map[p.x][p.y+1]=1; tw opt; opt.x=p.x; opt.y=p.y+1; dl.push(opt); } } return tot; } int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}; bool q[520][520]; int dfs(int w,int x,int y) { if(x==n) { a[w].l=min(a[w].l,y);a[w].r=max(a[w].r,y); } for(int i=0;i<=3;i++) { int xxx=x+dx[i]; int yyy=y+dy[i]; if(xxx<1||xxx>n||yyy<1||yyy>m) continue; if(high[xxx][yyy]<high[x][y]&&!q[xxx][yyy]) { q[xxx][yyy]=1; dfs(w,xxx,yyy); } } } int main() { int flag1=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&high[i][j]); int num=BFS(); if(num!=m) printf("0\n%d",m-num); else { for(int i=1;i<=m;i++) a[i].l=m+1,a[i].r=0; for(int i=1;i<=m;i++) { memset(q,0,sizeof(q)); q[1][i]=1; dfs(i,1,i); } sort(a+1,a+m+1,cmp); int i=m;while(a[i].l==m+1) i--; int maxn=0; int tot=0; while(maxn<m) { int wwww=maxn; for(int j=1;j<=i;j++) { if(a[j].l<=maxn+1) wwww=max(a[j].r,wwww); } tot++; maxn=wwww; } printf("1\n%d",tot); } return 0; }