http://poj.org/problem?id=3083題意就是在圖里遍歷遍歷：bfs+dfs.
哈哈，dfs，順時針和逆時針，學會這個好方法真好。
剛剛開始好惡心惡心的說，沒有找到好辦法，經驗太少了。嘿嘿，慢慢積累經驗哈。
代碼好丑，需要改改了：
#include<stdio.h>
#include<string.h>
#include<math.h>
int t,n,m,xs,ys,xx,yy,least,right,left,step;
int a[45][45],vis[45][45],que[20005][2];
int go[4][2]= {{-1,0},{0,1},{1,0},{0,-1}};
int bfs(int x,int y)
{
int head,tail,x1,y1,x2,y2,i;
head=0;
tail=1;
que[1][0]=x;
que[1][1]=y;
vis[x][y]=1;
while (head<tail)
{
head++;
x1=que[head][0];
y1=que[head][1];
for (i=0; i<4 ; i++ )
{
x2=x1+go[i][0];
y2=y1+go[i][1];
if (a[x2][y2]&&!vis[x2][y2])
{
tail++;
if (x2==xx&&y2==yy)
return vis[x1][y1]+1;
que[tail][0]=x2;
que[tail][1]=y2;
vis[x2][y2]=vis[x1][y1]+1;
}
}
}
}
int dfs(int g,int x,int y,int k) //這里確定下一步該走哪個方向。需要找到第一個可以走的方向。
{
int i,x1,y1,gg;
step=1;
while (x!=xx||y!=yy)
{
for (i=1; i<=4 ; i++ )
{
gg=(g+k*i+4)%4;
x1=x+go[gg][0];
y1=y+go[gg][1];
if (a[x1][y1]) //如果當前可走就break；
break;
}
step++;
g=(gg+2)%4; //由x,y向gg方向走去x1,y1，則是通過(gg+2)%4這個方向到達x1,y1的。然后循環迭代。
x=x1;
y=y1;
}
}
int init()
{
int i,j;
char st[50];
scanf("%d%d",&m,&n);
memset(a,0,sizeof(a));
for (i=1; i<=n ; i++ )
{
getchar();
scanf("%s",&st);
for (j=0; j<m ; j++ )
{
if (st[j]!='#')
a[i][j+1]=1;
if (st[j]=='S')
xs=i,ys=j+1;
if (st[j]=='E')
xx=i,yy=j+1;
}
}
}
int work()
{
int g;
memset(vis,0,sizeof(vis));
least=bfs(xs,ys);
if (xs==1)
g=0;
else if (ys==m)
g=1;
else if (xs==n)
g=2;
else
g=3;
dfs(g,xs,ys,1);
left=step;
dfs(g,xs,ys,-1);
right=step;
}
int main()
{
scanf("%d",&t);
while (t--)
{
init();
work();
printf("%d %d %d\n",left,right,least);
}
return 0;
}
額，bfs和dfs寫了好幾個咯，該學學剪枝啦。好多東西呢，