【NOIP2010】引水入城_综合

CJOJ P1094 - 【NOIP2010】引水入城

题意

??给定一个 $n*m$ 的网格，每个格子有一个高度 $H$ _{$i,j$ ，水能从高度高的地方流向高度低的地方（必须严格大于）。现在要从第一行选出若干个点，使得水流能从这些点出发，流到最后一行的每一个点，求最小的点数，如果有不能到达的点，输出不能到达的点的数量}

解法

宽搜+贪心：
??首先要判断能否全部覆盖，所以我们可以进行 $bfs$ 。
??依次对第一行的每一个点进行 $bfs$ 拓展，只往下走或者左右走。可以证明，如果在最后一排有地方需要往上走绕路才能到达，那么该情况无解（如图）：
??
??8–>7–>6–>5–>4–>3–>2–>1，要想从5到1，则必须往上绕路，那就说明中间的格子（6）比四周都高（5，3，1），那么水流就无法到达中间的格子，所以无解。
??由上也可以知道，第一行的一个点能够到达的格子必定是连续的，所以我们可以在 $bfs$ 的时候，将这个点能够控制的区间记下来。
??于是我们就能够得到 $m$ 个区间，我们要用这 $m$ 个区间去覆盖最后一行的m个点，采用贪心策略即可获得答案。
??另外，我们可以发现：只有一个点的高度大于等于它左右的点，那么这个点才有必要进行 $bfs$ 。
??因为如果它旁边的格子比它高，那么它能去的地方，它旁边的格子也能去，而且去得更多，也就更优。

复杂度

O（ $nm+km+mlogm$ ），k为常数

代码

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int MAXN=510;
struct node
{int rtx,rty;int x,y;
};
struct Section
{int l,r;bool operator < (const Section &a) const{return l==a.l ? r<a.r : l<a.l;}
}t[MAXN];
bool vis[MAXN][MAXN],to[MAXN];
int h[MAXN][MAXN];
int n,m,ans;
queue<node> q;
int X0[5]={
   0,-1,1,0,0};
int Y0[5]={
   0,0,0,1,-1};
void bfs(int lie)
{node tmp;int H;q.push( (node){ 1,lie,1,lie } );vis[1][lie]=1;while( !q.empty() ){tmp=q.front(),q.pop();if( tmp.x==n ){to[tmp.y]=1;t[tmp.rty].l=min( t[tmp.rty].l,tmp.y );t[tmp.rty].r=max( t[tmp.rty].r,tmp.y );}H=h[tmp.x][tmp.y];for(int k=1,x,y;k<=4;k++){x=tmp.x+X0[k],y=tmp.y+Y0[k];if( vis[x][y] || h[x][y]>=H )   continue ;if( x<1 || x>n || y>m || y<1 )   continue ;vis[x][y]=1;q.push( (node){ tmp.rtx,tmp.rty,x,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]);for(int i=1;i<=m;i++)   t[i].l=MAXN,t[i].r=0;for(int i=1;i<=m;i++)if( h[1][i]>=h[1][i-1] && h[1][i]>=h[1][i+1] ){memset( vis,0x0,sizeof vis );bfs( i );}for(int i=1;i<=m;i++)if( !to[i] )   ans++;if( ans ){printf("0\n%d\n",ans);return 0;}sort( t+1,t+m+1 );int r=0;for(int i=1,x;i<=m;i++){x=i;while( t[i+1].l<=r+1 && i+1<=m ){i++;if( t[i].r>t[x].r )   x=i;}r=t[x].r,ans++;if( r>=m )   break ;}printf("1\n%d\n",ans);return 0;
}