http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=682&pid=1003
中文题意，不再描述。
题解：
顺序给山峰出现的时间，明显地用二分来查找。然后连通块用并查集（也可以BFS，复杂度都是O（n））来维护。
1.并查集
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=505; char maze[maxn][maxn]; bool vis[maxn][maxn]; int n,m,q,par[maxn*maxn]; int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}; struct node { int x,y; }p[maxn*maxn]; int find(int x) { return x==par[x]?x:par[x]=find(par[x]); } void unite(int x,int y) { x=find(x); y=find(y); if(x==y) return ; par[x]=y; } bool check(int t) { for(int i=0;i<=n*m+1;i++) par[i]=i; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(maze[i][j]=='1') vis[i][j]=true; else vis[i][j]=false; for(int i=1;i<=t;i++) vis[p[i].x][p[i].y]=true; for(int i=1;i<=n;i++)//最上方编号为0,1-n行编号为1-n*m，最后一行（n+1）编号为n*m+1 for(int j=1;j<=m;j++) { if(vis[i][j]) continue; for(int k=0;k<4;k++) { int nx=i+dx[k],ny=j+dy[k]; if(ny<1||ny>m) continue; if(nx==0) unite((i-1)*m+j,0); else if(nx==n+1) unite((i-1)*m+j,n*m+1); else if(!vis[nx][ny]) unite((i-1)*m+j,(nx-1)*m+ny); } } if(find(0)==find(n*m+1)) return true; return false; } void solve() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",maze[i]+1); scanf("%d",&q); for(int i=1;i<=q;i++) { scanf("%d%d",&p[i].x,&p[i].y); p[i].x++,p[i].y++; } if(check(q))//不存在解 { cout<<"-1"<<endl; return ; } int l=1,r=q,ans=0; while(l<=r)//二分 { int mid=(l+r)/2; if(!check(mid)) { r=mid-1; ans=mid; } else l=mid+1; } cout<<ans<<endl; } int main() { int t; cin>>t; while(t--) { memset(vis,false,sizeof(vis)); solve(); } return 0; }
2.BFS
#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; const int maxn=505; char maze[maxn][maxn]; bool vis[maxn][maxn]; int n,m,q; int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}; struct node { int x,y; }p[maxn*maxn]; bool bfs() { queue<node> que; node cur; for(int i=1;i<=n;i++) { cur.x=0; cur.y=i; que.push(cur); } while(que.size()) { cur=que.front(); que.pop(); if(cur.x==n+1) return true; for(int i=0;i<4;i++) { node next=cur; next.x+=dx[i],next.y+=dy[i]; if(0<=next.x&&next.x<=n+1&&1<=next.y&&next.y<=m&&!vis[next.x][next.y]) { vis[next.x][next.y]=true; que.push(next); } } } return false; } bool check(int t) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(maze[i][j]=='1') vis[i][j]=true; else vis[i][j]=false; for(int i=1;i<=t;i++) vis[p[i].x][p[i].y]=true; return bfs(); } void solve() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",maze[i]+1); scanf("%d",&q); for(int i=1;i<=q;i++) { scanf("%d%d",&p[i].x,&p[i].y); p[i].x++,p[i].y++; } if(check(q)) { cout<<"-1"<<endl; return ; } int l=1,r=q,ans=0; while(l<=r) { int mid=(l+r)/2; if(!check(mid)) { r=mid-1; ans=mid; } else l=mid+1; } cout<<ans<<endl; } int main() { int t; cin>>t; while(t--) { memset(vis,false,sizeof(vis)); solve(); } return 0; }