poj 3083
题目大意#……# #.####.# #.####.# #.####.# #.####.# #…#..# #S#E####
求出从起点S到终点E的沿着左边墙(#)、右边墙、和最短距离。
分析 最短距离就是裸的BFS，沿左边墙和右边差不多，用DFS。用一个face变量来表示当前的面朝方向，关键是在某个位置是需要不断转向来判断面朝的方向是否能走。
总结 在写了几道BFS DFS后慢慢有点感觉了，一次AC率也提高了，还是比较开心的。BFS DFS的题就是经常代码有点长，但又一部分可以直接ctrlC ctrlV再修改下就行了。逻辑也还算清晰。
代码 #include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<queue> using namespace std; const int INF=999999999; int T; int w,h; int sx,sy; int tx,ty; int k[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//k[i][j],表示朝方向i走一格 0表示x的变化1表示y的变化 char grid[50][50]; int bj[50][50]; int ans1,ans2,ans3; int face;//0 1 2 3 表示面朝上 右 下 左 struct Node { int x; int y; int step; }; bool Is_Can(int x,int y)//判断是否可以走 { if(grid[x][y]=='.' || grid[x][y]=='E' ) return 1; else return 0; } int Turn_left(int x) { return (x-1+4)%4; } int Turn_right(int x) { return (x+1)%4; } void Init_face(int &face) { if(sx==1)face=1; else if(sx==w)face=3; else if(sy==1)face=0; else face=2; } int Dfsl(int x,int y,int face) /* 从(x,y)沿着左边墙走到终点的步数,包括起点 */ { if(x==tx && y== ty)return 1; for(int i=0;i<4;i++) { face=Turn_left(face);//左 if(Is_Can(x+k[face][0],y+k[face][1]))return Dfsl(x+k[face][0],y+k[face][1],face)+1; else { face=Turn_right(face);//前 if(Is_Can(x+k[face][0],y+k[face][1]))return Dfsl(x+k[face][0],y+k[face][1],face)+1; else { face=Turn_right(face);//右 if(Is_Can(x+k[face][0],y+k[face][1]))return Dfsl(x+k[face][0],y+k[face][1],face)+1; else { face=Turn_right(face);//后 if(Is_Can(x+k[face][0],y+k[face][1]))return Dfsl(x+k[face][0],y+k[face][1],face)+1; } } } } } int Dfsr(int x,int y,int face) /* 从(x,y)沿着左边墙走到终点的步数,包括起点 */ { if(x==tx && y== ty)return 1; for(int i=0;i<4;i++) { face=Turn_right(face);//右 if(Is_Can(x+k[face][0],y+k[face][1]))return Dfsr(x+k[face][0],y+k[face][1],face)+1; else { face=Turn_left(face);//前 if(Is_Can(x+k[face][0],y+k[face][1]))return Dfsr(x+k[face][0],y+k[face][1],face)+1; else { face=Turn_left(face);//左 if(Is_Can(x+k[face][0],y+k[face][1]))return Dfsr(x+k[face][0],y+k[face][1],face)+1; else { face=Turn_left(face);//后 if(Is_Can(x+k[face][0],y+k[face][1]))return Dfsr(x+k[face][0],y+k[face][1],face)+1; } } } } } void Bfs() { queue<Node>Q; Node s; s.x=sx;s.y=sy;s.step=1; bj[s.x][s.y]=1; Q.push(s); while(!Q.empty()) { Node temp=Q.front(); Q.pop(); int x=temp.x; int y=temp.y; int step=temp.step; if(x==tx && y==ty){ans3=step;return;} if(Is_Can(x+1,y) && !bj[x+1][y]) { Node temp2; temp2.x=x+1; temp2.y=y; temp2.step=step+1; Q.push(temp2); bj[x+1][y]=1; } if(Is_Can(x-1,y) && !bj[x-1][y]) { Node temp2; temp2.x=x-1; temp2.y=y; temp2.step=step+1; Q.push(temp2); bj[x-1][y]=1; } if(Is_Can(x,y+1) && !bj[x][y+1]) { Node temp2; temp2.x=x; temp2.y=y+1; temp2.step=step+1; Q.push(temp2); bj[x][y+1]=1; } if(Is_Can(x,y-1)&& !bj[x][y-1]) { Node temp2; temp2.x=x; temp2.y=y-1; temp2.step=step+1; Q.push(temp2); bj[x][y-1]=1; } } } int main() { scanf("%d",&T); int c; while(T--) { memset(bj,0,sizeof(bj)); scanf("%d%d",&w,&h); for(int j=h;j>=1;j--) { getchar(); for(int i=1;i<=w;i++) { scanf("%c",&grid[i][j]); if(grid[i][j]=='S'){sx=i;sy=j;} if(grid[i][j]=='E'){tx=i;ty=j;} } } Bfs(); Init_face(face); ans1=Dfsl(sx,sy,face); Init_face(face); ans2=Dfsr(sx,sy,face); cout<<ans1<<" "<<ans2<<" "<<ans3<<endl; } }