记录编号	192230	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.254 s
提交时间	2015-10-10 07:18:05	内存使用	5.34 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdlib>
 
using namespace std;
 
const int MAXN = 505;
const int gx[4]= {-1,0,1,0};
const int gy[4]= {0,1,0,-1};
 
int ans=0x3fffffff;
int n,m,cs,tot;
bool flag;
int f[MAXN];
int map[MAXN][MAXN];
bool vis[MAXN][MAXN];
int num[MAXN][MAXN];
 
struct at {
    int l,r,id;
} a[MAXN];
 
void bfs_judge() {
    queue< pair<int,int> > q;
    for(int i=1; i<=m; ++i)q.push(make_pair(1,i)),vis[1][i]=1;
    while(!q.empty()) {
        int ex=q.front().first;
        int ey=q.front().second;
        q.pop();
        for(int i=0; i<4; ++i) {
            int qx=ex+gx[i];
            int qy=ey+gy[i];
            if(qx<1||qy<1||qx>n||qy>m||vis[qx][qy]||map[ex][ey]<=map[qx][qy]) continue;
            vis[qx][qy]=1;
            q.push(make_pair(qx,qy));
        }
    }
    for(int i=1; i<=m; ++i)
        if(!vis[n][i]) {
            flag=1;
            tot++;
        }
    if(flag) {
        printf("0\n%d",tot);
        exit(0);
    }
}
 
void bfs(int x,int y) {
    memset(vis,0,sizeof(vis));
    queue < pair<int,int> > q;
    q.push(make_pair(x,y));
    vis[x][y]=1;
    a[num[x][y]].id=num[x][y];
    while(!q.empty()) {
        int ex=q.front().first;
        int ey=q.front().second;
        q.pop();
        for(int i=0; i<4; ++i) {
            int qx=ex+gx[i];
            int qy=ey+gy[i];
            if(qx<1||qy<1||qx>n||qy>m||vis[qx][qy]||map[ex][ey]<=map[qx][qy]) continue;
            vis[qx][qy]=1;
            q.push(make_pair(qx,qy));
        }
    }
    for(int i=1; i<=m; ++i)
        if(vis[n][i]) {
            a[num[x][y]].l=i;
            break;
        }
    for(int i=m; i>=1; i--) {
        if(vis[n][i]) {
            a[num[x][y]].r=i;
            break;
        }
    }
}
 
void dp() {
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=m;++i) {
        if(a[num[1][i]].l==1) {
            f[i]=1;
            continue;
        }
        for(int j=1;j<i;++j) {
            if(a[num[1][j]].r>=a[num[1][i]].l-1) {
                if(f[i]>f[j]+1) {
                    f[i]=f[j]+1;
                }
            }
        }
        if(a[num[1][i]].r==m) {
            ans=min(ans,f[i]);
        }
    }
    printf("1\n%d",ans);
}
 
int main() {
    freopen("flow.in","r",stdin);
    freopen("flow.out","w",stdout);
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; ++i) for(j=1; j<=m; ++j) num[i][j]=++cs;
    for(i=1; i<=n; ++i)  for(j=1; j<=m; ++j) scanf("%d",&map[i][j]);
    bfs_judge();
    for(i=1; i<=m; ++i) bfs(1,i);
    dp();
//  for(i=1;i<=m;++i) printf("%d %d\n",a[num[1][i]].l,a[num[1][i]].r);
}