【NOIP2010提高组】引水入城

首先进行一次多源bfs就可以标记统计出底部的格子有哪些走不到，输出。
如果可行再执行可到的程序。
算法核心：
推论：
由题可推：第一行的每一个格子能够到达的底部格子必为一个连续的子序列。
那么整道题就可以变成用尽量少的区间覆盖1到m的大区间。

如上图：l~r中的每一个A都能走到。因为若A能走到L,但不能走到x,则有h(x)>=h(L)。那么A到L和R的路径上的格子高度都大于等于x格。x就成为了被这两条路径包围的一个“凸起”，没有任何起点格子能够走到x，就返回了无法到达的情况。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<vector>
#define maxn 505
using namespace std;
struct data
{
int x,y;
    friend bool operator <(data a,data b)
    {
return a.x<b.x;
    }
}q[maxn*maxn],ss[maxn];

int n,m,front,rear,ns=0;
int h[maxn][maxn],vis[maxn][maxn];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};

void read(int &x)
{
x=0;
    bool ok=0;
    char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
while((ch>='0'&&ch<='9')||ch=='-')
    {
if(ch=='-') ok=1;
else x=x*10+ch-'0';
        ch=getchar();
    }
if(ok) x=-x;
}

void in()
{
read(n);
read(m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) read(h[i][j]);
}

void BFS(int s)
{
    memset(vis,0,sizeof(vis));

    front=rear=1;
q[rear++]=(data){1,s};
    vis[1][s]=1;

while(rear!=front)
    {
        data t=q[front++];
for(int i=0;i<4;i++)
        {
int di=t.x+dx[i],dj=t.y+dy[i];

if(di<1||di>n||dj<1||dj>m) continue;
if(h[di][dj]>=h[t.x][t.y]) continue;
if(vis[di][dj]) continue;

q[rear++]=(data){di,dj};
            vis[di][dj]=1;
        }
    }

int l=m+1,r=-1;
for(int i=1;i<=m;i++) if(vis[n][i])
    {
        l=min(l,i);
        r=max(r,i);
    }
    ss[++ns]=((data){l,r}); 
}

int check()
{
    memset(vis,0,sizeof(vis));

    front=rear=1;
for(int i=1;i<=m;i++)
    {
q[rear++]=(data){1,i};
        vis[1][i]=1;
    }

while(rear!=front)
    {
        data t=q[front++];
for(int i=0;i<4;i++)
        {
int di=t.x+dx[i],dj=t.y+dy[i];

if(di<1||di>n||dj<1||dj>m) continue;
if(h[di][dj]>=h[t.x][t.y]) continue;
if(vis[di][dj]) continue;

q[rear++]=(data){di,dj};
            vis[di][dj]=1;
        }
    }
int num=0;
for(int i=1;i<=m;i++) if(!vis[n][i]) num++;
return num;
}

void task_task()
{

}

void task()
{
if(check()>0)
    {
printf("0\n%d",check());
return;
    }
for(int i=1;i<=m;i++) BFS(i);
int ans=0;
int s=1,l=m;
sort(ss+1,ss+1+ns);
for(int i=1;i<=m;i++) if(ss[i].x<=s)
    {
int k=s;

for(int j=i;ss[j].x<=s;j++) k=max(k,ss[j].y);

        ans++;
s=k+1;
if(s>l) break;
    }
printf("1\n%d",ans);
}

int main()
{
//freopen("in.txt","r",stdin);
    in();
    task();
return 0;
}