#include<iostream>
using namespace std;
int move[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
char Maze[100][100];
int mark[100][100],m,n,sx,sy,ex,ey,minpath,lpath,rpath;

int seekpath(int a,int b)
{
	int wx,wy,locx,locy,x[10000][3],xtop=0,j;
	x[0][0]=2;x[0][1]=a;x[0][2]=b;
	while(xtop!=-1){
		minpath=x[0][0];
		locx=x[0][1];locy=x[0][2];
		for(int i=1;i<=xtop;i++){
			x[i-1][0]=x[i][0];x[i-1][1]=x[i][1];x[i-1][2]=x[i][2];
		}
		xtop--;
		for(j=0;j<4;j++){
			wx=locx+move[j][0];wy=locy+move[j][1];
			if((Maze[wx][wy]=='.'||Maze[wx][wy]=='E')&&mark[wx][wy]==0){mark[wx][wy]=1;break;}
		}
		while(j!=4){
			if(wx==ex&&wy==ey)return 1;
			x[xtop+1][1]=wx;x[xtop+1][2]=wy;x[xtop+1][0]=minpath+1;xtop++;
			for(j=j+1;j<4;j++){
				wx=locx+move[j][0];wy=locy+move[j][1];
				if((Maze[wx][wy]=='.'||Maze[wx][wy]=='E')&&mark[wx][wy]==0){mark[wx][wy]=1;break;}
			}
		}
	}
	return 0;
}

int seekpath2(int x,int y,int z,int judge)
{
	int i,g,h;
	if(x==ex&&y==ey)return 1;
	for(i=0;i<4;i++){
		g=x+move[z][0];h=y+move[z][1];
		if(Maze[g][h]=='.'||Maze[g][h]=='E'){
			if(judge==0){
				lpath++;if(z==0)z=4;
				if(seekpath2(g,h,z-1,0))return 1;
			}
			else{
				rpath++;if(z==3)z=-1;
				if(seekpath2(g,h,z+1,1))return 1;
			}
		}
		if(judge==0){z++;if(z==4)z=0;}
		else{z--;if(z==-1)z=3;}
	}
	return 0;
}

int main()
{
	int N,I;
	cin>>N;
	for(I=1;I<=N;I++){
		cin>>n>>m;
		for(int i=0;i<m+2;i++)
			for(int j=0;j<n+2;j++){
				if(i==0||j==0||i==m+1||j==n+1)Maze[i][j]='#';
				else cin>>Maze[i][j];
				if(Maze[i][j]=='S'){sx=i;sy=j;}
				if(Maze[i][j]=='E'){ex=i;ey=j;}
			}
		for(int i2=0;i2<m+2;i2++)
			for(int j2=0;j2<n+2;j2++)mark[i2][j2]=0;
		lpath=rpath=1;
		mark[sx][sy]=1;
		seekpath(sx,sy);
		seekpath2(sx,sy,0,0);
		seekpath2(sx,sy,0,1);
		cout<<lpath<<' '<<rpath<<' '<<minpath<<endl;
	}
	return 0;
}

• Re:AC，真不容易 (3) tangr206 2009-08-20 13:47:57