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[][];
int counts[][];//BFS记录最短距离
int n,m;//长，宽
bool flag1,flag2;//深搜的找到的标记
struct Node {
int x;
int y;
int step;
}node[][];
int startx,starty;//起点
int endx,endy;//终点
int BFS(int x,int y){
int dir[][]={{,},{-,},{,},{,-}};//四个方向
for(int i=;i<=;i++)
for(int j=;j<=;j++)//初始化
counts[i][j]=;
queue<Node>Q;
Node tt;
tt.x=x;tt.y=y;tt.step=;
Q.push(tt);
counts[x][y]=;//注意这里
while(!Q.empty()){
Node temp=Q.front();
Q.pop();
int xx=temp.x;
int yy=temp.y;
int step=temp.step;
for(int i=;i<;i++){//四个方向进行收索
if(xx+dir[i][]<=n&&xx+dir[i][]>=&&yy+dir[i][]<=m&&yy+dir[i][]>=){
if(map1[xx+dir[i][]][yy+dir[i][]]!='#'&&step+<counts[xx+dir[i][]][yy+dir[i][]]){
counts[xx+dir[i][]][yy+dir[i][]]=step+;
Node ttt;
ttt.x=xx+dir[i][];
ttt.y=yy+dir[i][];
ttt.step=step+;
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，左边为2，下边3，右边4
if(!flag1&&y->=&&map1[x][y-]!='#')//如果来自上边，则这次首先考录左边，就是2
return DFSL(x,y-,,num+);
if(!flag1&&x->=&&map1[x-][y]!='#')//一下同理
return DFSL(x-,y,,num+);
if(!flag1&&y+<=m&&map1[x][y+]!='#')
return DFSL(x,y+,,num+);
if(!flag1&&x+<=n&&map1[x+][y]!='#')
return DFSL(x+,y,,num+);
}
if(dir==){ if(!flag1&&x+<=n&&map1[x+][y]!='#')
return DFSL(x+,y,,num+);
if(!flag1&&y->=&&map1[x][y-]!='#')
return DFSL(x,y-,,num+);
if(!flag1&&x->=&&map1[x-][y]!='#')
return DFSL(x-,y,,num+);
if(!flag1&&y+<=m&&map1[x][y+]!='#')
return DFSL(x,y+,,num+);
}
if(dir==){ if(!flag1&&y+<=m&&map1[x][y+]!='#')
return DFSL(x,y+,,num+);
if(!flag1&&x+<=n&&map1[x+][y]!='#')
return DFSL(x+,y,,num+);
if(!flag1&&y->=&&map1[x][y-]!='#')
return DFSL(x,y-,,num+);
if(!flag1&&x->=&&map1[x-][y]!='#')
return DFSL(x-,y,,num+);
}
if(dir==){
if(!flag1&&x->=&&map1[x-][y]!='#')
return DFSL(x-,y,,num+);
if(!flag1&&y+<=m&&map1[x][y+]!='#')
return DFSL(x,y+,,num+);
if(!flag1&&x+<=n&&map1[x+][y]!='#')
return DFSL(x+,y,,num+);
if(!flag1&&y->=&&map1[x][y-]!='#')
return DFSL(x,y-,,num+);
}
}
return ;
}
int DFSR(int x,int y,int dir,int num){//向右搜索一样，同向左的同理。
if(x==endx&&y==endy){
flag2=true;
return num;
}
if(!flag2){
if(dir==){
if(!flag2&&y+<=m&&map1[x][y+]!='#')
return DFSR(x,y+,,num+);
if(!flag2&&x->=&&map1[x-][y]!='#')
return DFSR(x-,y,,num+);
if(!flag2&&y->=&&map1[x][y-]!='#')
return DFSR(x,y-,,num+);
if(!flag2&&x+<=n&&map1[x+][y]!='#')
return DFSR(x+,y,,num+);
}
if(dir==){
if(!flag2&&x->=&&map1[x-][y]!='#')
return DFSR(x-,y,,num+);
if(!flag2&&y->=&&map1[x][y-]!='#')
return DFSR(x,y-,,num+);
if(!flag2&&x+<=n&&map1[x+][y]!='#')
return DFSR(x+,y,,num+);
if(!flag2&&y+<=m&&map1[x][y+]!='#')
return DFSR(x,y+,,num+);
}
if(dir==){
if(!flag2&&y->=&&map1[x][y-]!='#')
return DFSR(x,y-,,num+);
if(!flag2&&x+<=n&&map1[x+][y]!='#')
return DFSR(x+,y,,num+);
if(!flag2&&y+<=m&&map1[x][y+]!='#')
return DFSR(x,y+,,num+);
if(!flag2&&x->=&&map1[x-][y]!='#')
return DFSR(x-,y,,num+);
}
if(dir==){
if(!flag2&&x+<=n&&map1[x+][y]!='#')
return DFSR(x+,y,,num+);
if(!flag2&&y+<=m&&map1[x][y+]!='#')
return DFSR(x,y+,,num+);
if(!flag2&&x->=&&map1[x-][y]!='#')
return DFSR(x-,y,,num+);
if(!flag2&&y->=&&map1[x][y-]!='#')
return DFSR(x,y-,,num+);
}
}
return ;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++){
for(int j=;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=;
printf("%d %d %d\n", DFSL(startx,starty,,),DFSR(startx,starty,,) ,BFS(startx,starty)+);
}
}