果然任何最后一题都是鬼畜树/图的题
可以发现第一排每个点能到的点是一段区间。。
于是几遍BFS就完了
第一遍从第一排BFS，判断有没有不可能的
第二遍从最后一排，从左往右BFS，找出第一排能到达的最后一排的最左端点
第三遍从最后一排，从右往左BFS，找出第一排能到达的最后一排的最右端点
最后排个序贪心下就行了
【写起来也是有够麻烦的
|
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 |
// <flow.cpp> - 02/14/16 15:45:23 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=502; int n,m; int h[MAXN][MAXN]; int vis[MAXN][MAXN]; int dp[MAXN][2]; queue <pair<int,int> > q; const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0}; bool check(int x,int y){return x>=1&&x<=n&&y>=1&&y<=m;} void bfs(bool f,int k){ q.push(make_pair(f?n:1,k)); while(!q.empty()){ int x=q.front().first,y=q.front().second;q.pop(); for(int i=0;i<4;i++){ int xx=x+dx[i],yy=y+dy[i]; if(!check(xx,yy)||vis[xx][yy])continue; if(!f&&h[x][y]<=h[xx][yy])continue; if(f&&h[x][y]>=h[xx][yy])continue; vis[xx][yy]=k; q.push(make_pair(xx,yy)); } } } void clear(){for(int i=1;i<=n;i++)for(int o=1;o<=m;o++)vis[i][o]=0;} struct C{int l,r;}c[MAXN]; bool cmp(C a,C b){return a.l==b.l?a.r<b.r:a.l<b.l;} int main(){ freopen("flow.in","r",stdin); freopen("flow.out","w",stdout); n=getint(),m=getint(); for(int i=1;i<=n;i++) for(int o=1;o<=m;o++) h[i][o]=getint(); for(int i=1;i<=m;i++)if(!vis[1][i]){vis[1][i]=i;bfs(0,i);} int no=0; for(int i=1;i<=m;i++)if(!vis[n][i])no++; if(no){printf("0\n%d",no);return 0;} clear();for(int i=1;i<=m;i++)if(!vis[n][i]){vis[n][i]=i;bfs(1,i);} for(int i=1;i<=m;i++)c[i].l=vis[1][i]; clear();for(int i=m;i>=1;i--)if(!vis[n][i]){vis[n][i]=i;bfs(1,i);} for(int i=1;i<=m;i++)c[i].r=vis[1][i]; for(int i=1;i<=m;i++){if(!c[i].l)c[i].l=c[i].r;if(!c[i].r)c[i].r=c[i].l;} sort(c+1,c+1+m,cmp); int now=0,to=0,tot=0; for(int i=1;i<=m;i++){ if(now+1>=c[i].l)to=max(to,c[i].r); else now=to,to=max(to,c[i].r),tot++; } if(now!=m)tot++; printf("1\n%d",tot); return 0; } |
说点什么