「BZOJ1687」[Usaco2005 Open] Navigating the City 城市交通
Description
由于牛奶市场的需求，奶牛必须前往城市，但是唯一可用的交通工具是出租车．教会奶牛如何在城市里打的．
给出一个城市地图，东西街区E(1≤E≤40)，南北街区N(1≤N≤30).制作一个开车指南给出租车司机，告诉他如何从起点（用S表示）到终点（用E表示）．每一个条目用空格分成两部分，第一个部分是方向（N，E，S，W之一），第二个是一个整数，表示要沿着这个方向开几个十字路口．如果存在多条路线，你应该给出最短的．数据保证，最短的路径存在且唯一． 地图中“+”表示十字路口，道路用“I”和“一”表示．建筑和其他设施用“．”表示．下面是一张地图：
出租车可以沿着东，北，西，北，东开两个十字路口，以此类推．具体将由样例给出
Input
第1行：两个用空格隔开的整数N和E.
第2到2N行：每行有2E-I个字符，表示地图．
Output
每行有一个表示方向的字母和一个表示要开几个十字路口的数字表示．
Sample Input
Sample Input
Sample Output
E 1
N 1
W 1
N 1
E 2
S 1
E 3
S 1
W 1
N 1
W 1
N 1
E 2
S 1
E 3
S 1
W 1
题解
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 |
#include<iostream> #include<cstdio> using namespace std; int n,m,t,w=1,bx,by,ex,ey; int ans,ans1[10001],ans2[10001]; int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; bool mp[101][101],mark[101][101]; char ch[101],dir[5]={' ','S','N','E','W'}; struct que{int x,y,from;}q[10001]; void bfs() { q[0].x=bx;q[0].y=by; mark[bx][by]=1; while(t<w) { int x=q[t].x,y=q[t].y; for(int k=0;k<4;k++) { int nowx=x+xx[k],nowy=y+yy[k]; if(!mp[nowx][nowy])continue; nowx=nowx+xx[k],nowy=nowy+yy[k]; if(!mp[nowx][nowy]||mark[nowx][nowy])continue; mark[nowx][nowy]=1; q[w].x=nowx;q[w].y=nowy;q[w].from=t;w++; if(nowx==ex&&nowy==ey)return; } t++; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<n*2;i++) { scanf("%s",ch); for(int j=0;j<m*2-1;j++) { if(ch[j]=='.')continue; if(ch[j]=='S'){bx=i;by=j+1;} if(ch[j]=='E'){ex=i;ey=j+1;} mp[i][j+1]=1; } } bfs();w--; int flag=0,d,dis=0; while(w) { int now=q[w].from; if(q[w].x>q[now].x)d=1; if(q[w].x<q[now].x)d=2; if(q[w].y>q[now].y)d=3; if(q[w].y<q[now].y)d=4; if(d!=flag) { if(flag!=0){ans++;ans1[ans]=flag;ans2[ans]=dis;} dis=1; flag=d; } else dis++; w=now; } ans++;ans1[ans]=flag;ans2[ans]=dis; for(int i=ans;i>0;i--) printf("%c %d\n",dir[ans1[i]],ans2[i]); return 0; } |
Subscribe