题意：给你一个迷宫，入口处标为S，出口处标为E，可以走的地方为“.”,不可以走的地方为#，求左转优先时从出口到入口的路程，再求右转优先时，出口到入口的路程，最后求从出口到入口的最短路程。
思路：求前两个的时候用DFS递归求解能走的路就OK，求最短的时候当然要用广度优先搜索啦。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
char ch[][];
int sum ;//总步数
int h,w,i,j,k ;
int enx,eny,stax,stay;
int fx[] = {,,,-};//列的变化，从0开始顺时针变化
int fy[] = {,,-,};//行的变化，从0开始顺时针变化
int lef[] = {,,,};//左转优先时，标记上下左右4个方向分别为0213；
int rig[] = {,,,};//右转优先时，右边为1；
struct node
{
int xz,yz;
int cnt;
} sh[];//数组模拟队列
void DFS(int dire,int x,int y,int d)//这个点的初始方向，这个点现在坐标，以及是左先还是右先
{
if(x == enx&&y == eny)//如果遍历到了'E'所在坐标，就结束掉遍历，返回
{
printf("%d",sum);
return ;
}
int xx,yy;
sum++;
if(d == )//左转优先
{
for(i = ; i <= ; i++)//4个方向遍历一遍
{
j = (dire+lef[i])%;//求出当前位置的方向数字
xx = x+fx[j];//传过来的参数x为原来的坐标j
yy = y+fy[j];
if(xx>=&&xx< h&&yy>=&&yy< w&&ch[yy][xx] != '#')//继续遍历的条件是不为#且没越出边界，要注意xx是到h为边界的与主函数中对应
{
DFS(j,xx,yy,);//继续递归下去
return ;
}
}
}
else
{
for(i = ; i <= ; i++)
{
j = (dire+rig[i])%;
xx = x+fx[j];
yy = y+fy[j];
if(xx>= && xx < h&&yy>= && yy < w&&ch[yy][xx] != '#')
{
DFS(j,xx,yy,);
return ;
}
}
}
}
void BFS(int x,int y)//广度优先搜索是队列，深度优先搜索是栈，深度是递归
{
int zh[][] = {};//标记数组，初始化为0，表示节点未被访问过
int le = ,ri = ;
zh[y][x] = ;
//将当前点坐标压入队列，后边进行处理
sh[].xz = x;
sh[].yz = y ;
sh[].cnt = ;
while(le < ri)
{
x = sh[le].xz;//从队列中取出进行操作
y = sh[le].yz ;
sum = sh[le++].cnt;
for(k = ; k <= ; k++)
{
//点的坐标
i = y+fy[k];
j = x+fx[k];
if(i>= && i<w && j<h && j>= && !zh[i][j] &&ch[i][j]!='#')//在原有条件下，还要保证节点没有被访问过
{
if(j == enx&&i == eny)//如果找到'E'就输出长度
{
cout<<sum+<<endl;
return ;
}
zh[i][j] = ;//表示这个节点已经被访问过了，标记为1
//将这个点加入队列用来以后进行访问这个点四周的点
sh[ri].yz = i;
sh[ri].xz = j;
sh[ri].cnt = sum+;//这个点步数加1
ri++;//while循环结束的条件就是该点不符合条件，ri不再累加
}
}
}
}
int main()
{
int n,dire;
scanf("%d",&n);
while(n--)
{
scanf("%d %d",&h,&w);//h是列，w是行
for(i = ; i <= w- ; i++)
{
scanf("%s",ch[i]);
for(j = ; j <= h- ; j++)
{
if(ch[i][j] == 'S')
{
stax = j;
stay = i;
}
if(ch[i][j] == 'E')
{
enx = j;
eny = i ;
}
}
}
if(stax == ) dire = ;//左
if(stax == h-) dire = ;//右
if(stay == ) dire = ;//上
if(stay == w-) dire = ;//下
sum = ;//初始化
DFS(dire,stax,stay,);//左转优先
printf(" ");
sum = ;//初始化
DFS(dire,stax,stay,);//右转优先
printf(" ");
BFS(stax,stay);//求最短的用bfs
}
return ;
}