题解
看到网上很多dfs，bfs，记忆化搜索的代码（其实这个主要也是深搜），但是本校大佬@Ajsoabk用了一个神奇的方法，把它转化成一个线段覆盖的问题。
首先用了一便深搜，如果所有的蓄水池都建了，能不能满足要求，不满足就直接输出，满足说明肯定有解，下一步。
确保了有解之后，我们就可以从每个能建蓄水池的城市出发，走到沙漠城市，能够走到的沙漠城市一定是一段连续的区间（要不然就不会有解），我们求出这些区间，然后统计答案即可
注释说的比较详细了
代码
|
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 71 72 73 |
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int MAXN=500+5,inf=0x7fffffff; const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; /* vis[i][j]用来标记(i,j)是否访问过 */ bool vis[MAXN][MAXN],used[MAXN]; /* used[i]表示第i个能造蓄水池的城市有没有被遍历 */ /* pos[i]表示在覆盖i点的线段中，最右边的点 */ /* l[i][j],r[i][j]分别表示(i,j)能走到的最左，最右点 */ int n,m,h[MAXN][MAXN],pos[MAXN],cnt,now,l[MAXN][MAXN],r[MAXN][MAXN]; inline bool jud(const int &x,const int &y){ return x>0&&x<=n&&y>0&&y<=m; } void dfs(int x,int y){ int nx,ny; vis[x][y]=1; if(x==1)used[y]=1; if(x==n)l[x][y]=r[x][y]=y; for(int i=0;i<4;++i){//四个方向走 nx=x+dir[i][0]; ny=y+dir[i][1]; if(jud(nx,ny)&&h[nx][ny]<h[x][y]){//合法 if(!vis[nx][ny])//没被访问过 dfs(nx,ny); if(l[x][y]>l[nx][ny])l[x][y]=l[nx][ny];//更新左右端点 if(r[x][y]<r[nx][ny])r[x][y]=r[nx][ny]; } } } void dfs1(int x,int y){ vis[x][y]=1; int nx,ny; for(int i=0;i<4;++i){ nx=x+dir[i][0]; ny=y+dir[i][1]; if(jud(nx,ny)&&h[nx][ny]<h[x][y]&&vis[nx][ny]==0)dfs1(nx,ny); } } int main(){ cin>>n>>m; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>h[i][j]; /* 判断是否可行 如果全部都建了蓄水池还不行，那就无解 */ for(int i=1;i<=m;++i)if(!vis[1][i])dfs1(1,i); for(int i=1;i<=m;++i)if(!vis[n][i])cnt++; if(cnt){ printf("0\n%d\n",cnt); return 0; } /* END */ memset(vis,0,sizeof(vis)); memset(l,0x3f,sizeof(l)); for(int i=1;i<=m;++i){ if(!used[i]){ dfs(1,i); for(int j=l[1][i];j<=r[1][i];++j)if(pos[j]<r[1][i])pos[j]=r[1][i];//更新pos } } for(now=1;now!=m+1;now=pos[now]+1)++cnt;//累计答案 printf("1\n%d\n",cnt); return 0; } |