【题解】[Nwerc 2006]escape -C++
Description 2 5 6 0 0 4 0 2 1 2 3 Sample Output 2 14 这周考试的第三题... #include<bits/stdc++.h> #define FAST_IN std::ios::sync_with_stdio(false);cin.tie(NULL); using namespace std; int x,y,n,sx,sy,ex,ey,step; inline int hl/*howlong*/(int a,int b,int c,int d) { return abs(a-c)+abs(b-d); } struct node { int x,t; }; int best[1010][1010]; bool vis[1010][1010]; int dir[4][2]={{1,0},{-1,{0,1},-1}}; queue<node> s; void bfs1() { while(!s.empty()) { node now=s.front(); s.pop(); for(int i=0;i<4;i++) { int tx=now.x+dir[i][0]; int ty=now.y+dir[i][1]; if(tx>=0&&ty>=0&&tx<x&&ty<y&&!best[tx][ty]) { best[tx][ty]=now.t+1; s.push((node){tx,ty,now.t+1}); } } } } bool bfs(int left) { if(best[sx][sy]-1<left)return 0; memset(vis,sizeof(vis)); queue<node> q; q.push((node){sx,0}); vis[sx][sy]=1; while(!q.empty()) { node now=q.front(); q.pop(); if(now.x==ex&&now.y==ey) { step=now.t; return 1; } for(int i=0;i<4;i++) { int tx=now.x+dir[i][0],ty=now.y+dir[i][1]; if(best[tx][ty]-1<left)continue; if(!vis[tx][ty]&&best[tx][ty]-1>=left&&0<=tx&&tx<x&&0<=ty&&ty<y) { q.push((node){tx,now.t+1}); vis[tx][ty]=1; } } } return 0; } int main() { FAST_IN; scanf("%d%d%d%d%d%d%d",&n,&x,&y,&sx,&sy,&ex,&ey); for(int i=1;i<=n;i++) { int tx,ty; scanf("%d%d",&tx,&ty); best[tx][ty]=1; s.push((node){tx,1}); } bfs1(); // for(int i=0;i<x;i++) // { // for(int j=0;j<y;j++) // { // cout<<best[i][j]; // } // cout<<endl; // } int l=0,r=best[ex][ey]; while(l<r) { int mid=(l+r)/2; if(bfs(mid))l=mid+1; else r=mid; } cout<<r-1<<" "<<step<<endl; return 0; } ov. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |