#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
char map[50][50];
int step[50][50];
int dir[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
int lDFS(int i,int j,int s,int now)
{
	if(map[i][j]=='E')return s;
	for(int d=now;d<now+4;++d)
	{
		int di=i+dir[d%4][0];
		int dj=j+dir[d%4][1];
		if(d<=0)d+=4;
		if(map[di][dj]!='#')return lDFS(di,dj,s+1,(d-1)%4);
		d%=4;
	}
	return -1;
}
int rDFS(int i,int j,int s,int now)
{
	if(map[i][j]=='E')return s;
	for(int d=now+4;d>now;--d)
	{
		int di=i+dir[d%4][0];
		int dj=j+dir[d%4][1];
		if(map[di][dj]!='#')return rDFS(di,dj,s+1,(d+1)%4);
	}
	return -1;
}
typedef struct Coo
{
	int x,y;
}coordinate;
int BFS(int i,int j)
{
	queue<coordinate> C;
	coordinate t;
	t.x=i,t.y=j;
	C.push(t);
	step[t.x][t.y]=1;
	while(!C.empty())
	{
		t=C.front();
		C.pop();
		if(map[t.x][t.y]=='E')return step[t.x][t.y];
		coordinate temp;
		for(int d=0;d<4;++d)
		{
			temp=t;
			temp.x+=dir[d][0];
			temp.y+=dir[d][1];
			if(map[temp.x][temp.y]!='#' && !step[temp.x][temp.y]){ C.push(temp);step[temp.x][temp.y]=step[t.x][t.y]+1;}
		}
	}
	return -1;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int r,l;
		cin>>l>>r;
		int s_i,s_j,e_i,e_j;
		memset(map,'#',sizeof(map));
		memset(step,0,sizeof(step));
		for(int i=1;i<=r;++i)
		{
			for(int j=1;j<=l;++j)
			{
				cin>>map[i][j];
				if(map[i][j]=='S')s_i=i,s_j=j;
				if(map[i][j]=='E')e_i=i,e_j=j;
			}
		}
		cout<<lDFS(s_i,s_j,1,0)<<" "<<rDFS(s_i,s_j,1,0)<<" "<<BFS(s_i,s_j)<<endl;


	}
	return 0;
}

• Re:今天又改了一下这道题，改成0ms了 (1573) TSERROF 2012-10-29 23:08:32