---恢复内容开始---
http://poj.org/problem?id=3083
题目大意就是给你要你从S走到E，且只有.代表的地方才是可以走的，有三种方式的走法。
一、是向左优先转，从S到E的步数。
二、是向右优先转，从S到E的步数。
三、S到E的最短路径，小于等于前面二者。
思路：这题比较难的就是怎么确定方向，对于向左走的人。它的右边对于我们来说是向上的，解决这个办法可以用数字来模拟方向
| 0 | ||
| 1 | 当前位置 | 3 |
| 2 |
当你的是从3走到当前位置时，对于你来说，你的左边就是2，右边就是0，
而当你的优先偏转方向是#也就是不能走时，你应该按原方向走，意思就是对于左优先你走的顺序应该2 1 0 3
右优先就是0 1 2 3 而不是0 3 2 1
我的代码也是借鉴了别人的，比较繁琐，但是思路比较清晰，个人觉得比较好理解
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <queue> using namespace std; queue<int >first; //定义两个队列，用来分别存位置当前位置，当然也可以用pair类型，那样定义一个就可以了
queue<int >second;
char str[][];
int lstep,rstep,bstep[][];
bool mark[][]; //用来标记走过的，在前两个搜索时不需要用，因为有可能会走原路，用在第三个求最短路径
int lbfs(int i,int j,int d) //向左优先转
{
lstep++;
if(str[i][j]=='E') return ;
switch(d)
{
case :
{
if(str[i][j-]=='.'||str[i][j-]=='E') //记得要加==‘E’，不然它是永远也找不到E的
lbfs(i,j-,);
else if(str[i-][j]=='.'||str[i-][j]=='E')
lbfs(i-,j,);
else if(str[i][j+]=='.'||str[i][j+]=='E')
lbfs(i,j+,);
else if(str[i+][j]=='.'||str[i+][j]=='E')
lbfs(i+,j,);
break;
}
case :
{
if(str[i+][j]=='.'||str[i+][j]=='E')
lbfs(i+,j,);
else if(str[i][j-]=='.'||str[i][j-]=='E')
lbfs(i,j-,);
else if(str[i-][j]=='.'||str[i-][j]=='E')
lbfs(i-,j,);
else if(str[i][j+]=='.'||str[i][j+]=='E')
lbfs(i,j+,);
break;
}
case :
{
if(str[i][j+]=='.'||str[i][j+]=='E')
lbfs(i,j+,);
else if(str[i+][j]=='.'||str[i+][j]=='E')
lbfs(i+,j,);
else if(str[i][j-]=='.'||str[i][j-]=='E')
lbfs(i,j-,);
else if(str[i-][j]=='.'||str[i-][j]=='E')
lbfs(i-,j,);
break;
}
case :
{
if(str[i-][j]=='.'||str[i-][j]=='E')
lbfs(i-,j,);
else if(str[i][j+]=='.'||str[i][j+]=='E')
lbfs(i,j+,);
else if(str[i+][j]=='.'||str[i+][j]=='E')
lbfs(i+,j,);
else if(str[i][j-]=='.'||str[i][j-]=='E')
lbfs(i,j-,);
break;
}
}
return ;
}
int rbfs(int i,int j,int d)
{
rstep++;
if(str[i][j]=='E') return ;
switch(d)
{
case :
{
if(str[i][j+]=='.'||str[i][j+]=='E')
rbfs(i,j+,);
else if(str[i-][j]=='.'||str[i-][j]=='E')
rbfs(i-,j,);
else if(str[i][j-]=='.'||str[i][j-]=='E')
rbfs(i,j-,);
else if(str[i+][j]=='.'||str[i+][j]=='E')
rbfs(i+,j,);
break;
}
case :
{
if(str[i-][j]=='.'||str[i-][j]=='E')
rbfs(i-,j,);
else if(str[i][j-]=='.'||str[i][j-]=='E')
rbfs(i,j-,);
else if(str[i+][j]=='.'||str[i+][j]=='E')
rbfs(i+,j,);
else if(str[i][j+]=='.'||str[i][j+]=='E')
rbfs(i,j+,);
break;
}
case :
{
if(str[i][j-]=='.'||str[i][j-]=='E')
rbfs(i,j-,);
else if(str[i+][j]=='.'||str[i+][j]=='E')
rbfs(i+,j,);
else if(str[i][j+]=='.'||str[i][j+]=='E')
rbfs(i,j+,);
else if(str[i-][j]=='.'||str[i-][j]=='E')
rbfs(i-,j,);
break;
}
case :
{
if(str[i+][j]=='.'||str[i+][j]=='E')
rbfs(i+,j,);
else if(str[i][j+]=='.'||str[i][j+]=='E')
rbfs(i,j+,);
else if(str[i-][j]=='.'||str[i-][j]=='E')
rbfs(i-,j,);
else if(str[i][j-]=='.'||str[i][j-]=='E')
rbfs(i,j-,);
break;
}
}
return ;
}
int dfs(int i,int j)
{
memset(mark,false,sizeof(mark)); //切记对这些数值都要进行清零，还有对队列要记得清空，不然很容易出问题
memset(bstep,,sizeof(bstep));
bstep[i][j]=;
while(!first.empty())
{
first.pop();
second.pop();
}
int he,ba;
first.push(i);
second.push(j);
mark[i][j]=true;
while(!first.empty())
{
he=first.front();
first.pop();
ba=second.front();
second.pop();
if(str[he][ba]=='E')
{
printf(" %d\n",bstep[he][ba]);
break;
}
if((str[he+][ba]=='.'||str[he+][ba]=='E')&&!mark[he+][ba]) //对于没走过的路又可以走的路进行标记，这样可以确定这个路是最短的。
{
first.push(he+);
second.push(ba);
mark[he+][ba]=true;
bstep[he+][ba]=bstep[he][ba]+;
}
if((str[he][ba+]=='.'||str[he][ba+]=='E')&&!mark[he][ba+])
{
first.push(he);
second.push(ba+);
mark[he][ba+]=true;
bstep[he][ba+]=bstep[he][ba]+;
}
if((str[he][ba-]=='.'||str[he][ba-]=='E')&&!mark[he][ba-])
{
first.push(he);
second.push(ba-);
mark[he][ba-]=true;
bstep[he][ba-]=bstep[he][ba]+;
}
if((str[he-][ba]=='.'||str[he-][ba]=='E')&&!mark[he-][ba])
{
first.push(he-);
second.push(ba);
mark[he-][ba]=true;
bstep[he-][ba]=bstep[he][ba]+;
}
}
return ;
}
int main()
{
int n,m,t,i,j,k,start;
scanf("%d",&t);
while(t)
{
t--;
memset(str,,sizeof(str));
lstep=;
rstep=;
scanf("%d%d",&m,&n);
for(i=;i<=n;i++)
scanf("%s",str[i]);
for(i=,k=;i<=n;i++)
{
for(j=;j<m;j++)
if(str[i][j]=='S')
{
k=;
break;
}
if(k==) break;
}
bstep[i][j]=;
if(i==n) start=;
else if(j==m-) start=;
else if(i==) start=;
else start=;
switch(start)
{
case :{ lbfs(i-,j,);break;} case :{ lbfs(i,j-,);break;} case :{ lbfs(i+,j,);break;} case :{ lbfs(i,j+,);break;}
}
switch(start)
{
case :{ rbfs(i-,j,);break;} case :{ rbfs(i,j-,);break;} case :{ rbfs(i+,j,);break;} case :{ rbfs(i,j+,);break;}
}
printf("%d %d",lstep,rstep);
dfs(i,j);
}
return ;
}