poj3083:http://poj.org/problem?id=3083
题意：给你一个迷宫，然后给你一个起点和终点，现在给你种规则，一种是先向左，无法向左则向前，无法向前则向右，否则则向后，另外一种就是求最短路程，然后一种就先向右，向前，向左，向后，分别求出这三种情况下所走的路程。
题解：求最短的路程只需BFS即可，先向左可以DFS，每次DFS记录来自的方向，对于不同的方向，采取不同的搜索顺序，即可。向右的同理。
#include<cstring> #include<cstdio> #include<iostream> #include<algorithm> #include<queue> using namespace std; char map1[42][42]; int counts[42][42];//BFS记录最短距离 int n,m;//长，宽 bool flag1,flag2;//深搜的找到的标记 struct Node { int x; int y; int step; }node[42][42]; int startx,starty;//起点 int endx,endy;//终点 int BFS(int x,int y){ int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//四个方向 for(int i=1;i<=41;i++) for(int j=1;j<=41;j++)//初始化 counts[i][j]=1000000; queue<Node>Q; Node tt; tt.x=x;tt.y=y;tt.step=0; Q.push(tt); counts[x][y]=0;//注意这里 while(!Q.empty()){ Node temp=Q.front(); Q.pop(); int xx=temp.x; int yy=temp.y; int step=temp.step; for(int i=0;i<4;i++){//四个方向进行收索 if(xx+dir[i][0]<=n&&xx+dir[i][0]>=1&&yy+dir[i][1]<=m&&yy+dir[i][1]>=1){ if(map1[xx+dir[i][0]][yy+dir[i][1]]!='#'&&step+1<counts[xx+dir[i][0]][yy+dir[i][1]]){ counts[xx+dir[i][0]][yy+dir[i][1]]=step+1; Node ttt; ttt.x=xx+dir[i][0]; ttt.y=yy+dir[i][1]; ttt.step=step+1; Q.push(ttt); } } } } return counts[endx][endy]; } int DFSL(int x,int y,int dir,int num){//dir表示方向，num表示当前的深度 if(x==endx&&y==endy){ flag1=true; return num; } if(!flag1){ if(dir==1){//这里定义向上为1，左边为2，下边3，右边4 if(!flag1&&y-1>=1&&map1[x][y-1]!='#')//如果来自上边，则这次首先考录左边，就是2 return DFSL(x,y-1,2,num+1); if(!flag1&&x-1>=1&&map1[x-1][y]!='#')//一下同理 return DFSL(x-1,y,1,num+1); if(!flag1&&y+1<=m&&map1[x][y+1]!='#') return DFSL(x,y+1,4,num+1); if(!flag1&&x+1<=n&&map1[x+1][y]!='#') return DFSL(x+1,y,3,num+1); } if(dir==2){ if(!flag1&&x+1<=n&&map1[x+1][y]!='#') return DFSL(x+1,y,3,num+1); if(!flag1&&y-1>=1&&map1[x][y-1]!='#') return DFSL(x,y-1,2,num+1); if(!flag1&&x-1>=1&&map1[x-1][y]!='#') return DFSL(x-1,y,1,num+1); if(!flag1&&y+1<=m&&map1[x][y+1]!='#') return DFSL(x,y+1,4,num+1); } if(dir==3){ if(!flag1&&y+1<=m&&map1[x][y+1]!='#') return DFSL(x,y+1,4,num+1); if(!flag1&&x+1<=n&&map1[x+1][y]!='#') return DFSL(x+1,y,3,num+1); if(!flag1&&y-1>=1&&map1[x][y-1]!='#') return DFSL(x,y-1,2,num+1); if(!flag1&&x-1>=1&&map1[x-1][y]!='#') return DFSL(x-1,y,1,num+1); } if(dir==4){ if(!flag1&&x-1>=1&&map1[x-1][y]!='#') return DFSL(x-1,y,1,num+1); if(!flag1&&y+1<=m&&map1[x][y+1]!='#') return DFSL(x,y+1,4,num+1); if(!flag1&&x+1<=n&&map1[x+1][y]!='#') return DFSL(x+1,y,3,num+1); if(!flag1&&y-1>=1&&map1[x][y-1]!='#') return DFSL(x,y-1,2,num+1); } } return 0; } int DFSR(int x,int y,int dir,int num){//向右搜索一样，同向左的同理。 if(x==endx&&y==endy){ flag2=true; return num; } if(!flag2){ if(dir==1){ if(!flag2&&y+1<=m&&map1[x][y+1]!='#') return DFSR(x,y+1,4,num+1); if(!flag2&&x-1>=1&&map1[x-1][y]!='#') return DFSR(x-1,y,1,num+1); if(!flag2&&y-1>=1&&map1[x][y-1]!='#') return DFSR(x,y-1,2,num+1); if(!flag2&&x+1<=n&&map1[x+1][y]!='#') return DFSR(x+1,y,3,num+1); } if(dir==2){ if(!flag2&&x-1>=1&&map1[x-1][y]!='#') return DFSR(x-1,y,1,num+1); if(!flag2&&y-1>=1&&map1[x][y-1]!='#') return DFSR(x,y-1,2,num+1); if(!flag2&&x+1<=n&&map1[x+1][y]!='#') return DFSR(x+1,y,3,num+1); if(!flag2&&y+1<=m&&map1[x][y+1]!='#') return DFSR(x,y+1,4,num+1); } if(dir==3){ if(!flag2&&y-1>=1&&map1[x][y-1]!='#') return DFSR(x,y-1,2,num+1); if(!flag2&&x+1<=n&&map1[x+1][y]!='#') return DFSR(x+1,y,3,num+1); if(!flag2&&y+1<=m&&map1[x][y+1]!='#') return DFSR(x,y+1,4,num+1); if(!flag2&&x-1>=1&&map1[x-1][y]!='#') return DFSR(x-1,y,1,num+1); } if(dir==4){ if(!flag2&&x+1<=n&&map1[x+1][y]!='#') return DFSR(x+1,y,3,num+1); if(!flag2&&y+1<=m&&map1[x][y+1]!='#') return DFSR(x,y+1,4,num+1); if(!flag2&&x-1>=1&&map1[x-1][y]!='#') return DFSR(x-1,y,1,num+1); if(!flag2&&y-1>=1&&map1[x][y-1]!='#') return DFSR(x,y-1,2,num+1); } } return 0; } int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d%d",&m,&n); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>map1[i][j]; if(map1[i][j]=='S'){ startx=i; starty=j; } if(map1[i][j]=='E'){ endx=i; endy=j; } } } flag1=flag2=0; printf("%d %d %d ", DFSL(startx,starty,1,1),DFSR(startx,starty,3,1) ,BFS(startx,starty)+1); } }