记录编号	323169	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.625 s
提交时间	2016-10-16 06:16:33	内存使用	4.19 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=505;
int n,m;
int h[maxn][maxn];
int T;
int vis[maxn][maxn];
struct point{
    int x,y;
    point(int _x,int _y){
        x=_x;y=_y;
    }
    point(){
    }
}q[maxn*maxn];int head,tail;
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int l[maxn],r[maxn],f[maxn],seq[maxn];
bool cmp(const int &a,const int &b){
    return l[a]<l[b];
}
void bfs(int x0,int y0){
    head=tail=0;
    q[tail++]=point(x0,y0);
    vis[x0][y0]=++T;
    int _x,_y;
    while(head!=tail){
        point tmp=q[head++];
        for(int i=0;i<4;++i){
            _x=tmp.x+d[i][0];_y=tmp.y+d[i][1];
            if(vis[_x][_y]!=T&&h[_x][_y]<h[tmp.x][tmp.y]){
                vis[_x][_y]=T;
                q[tail++]=point(_x,_y);
            }
        }
    }
}
int min(int a,int b){
    return a<b?a:b;
}
int main(){
    freopen("flow.in","r",stdin);
    freopen("flow.out","w",stdout);
    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<=n;++i)h[i][0]=h[i][m+1]=0x7fffffff;
    for(int i=1;i<=m;++i)h[0][i]=h[n+1][i]=0x7fffffff;
    bool flag=true;
    for(int i=1;i<=m;++i){
        bfs(1,i);
        for(int j=1;j<=m;++j){
            if(vis[n][j]==T){
                l[i]=j;
                break;
            }
        }
        for(int j=m;j>=1;--j){
            if(vis[n][j]==T){
                r[i]=j;
                break;
            }
        }
    }
    int cnt=0;
    for(int i=1;i<=m;++i){
        if(!vis[n][i])cnt++;
    }
    if(cnt!=0){  
         printf("0\n%d\n",cnt);
         fclose(stdin);fclose(stdout);
         return 0;
    }
    for(int i=1;i<=m;++i)seq[i]=i;
    sort(seq+1,seq+m+1,cmp);
    memset(f,0x3f,sizeof(f));
    f[1]=0;
    for(int i=1;i<=m;++i){
        for(int j=m;j>=1;--j){
            f[j]=min(f[j],f[j+1]);
        }
        if(l[i])f[r[i]+1]=min(f[r[i]+1],f[l[i]]+1);
    }
    printf("1\n%d\n",f[m+1]);
        
    
    fclose(stdin);fclose(stdout);
    return 0;
}