POJ3083--Children of the Candy Corn

BFSでは検索した状態を変えることを忘れてデッドサイクルに陥り、数日の間違いを調べてやっと見つけた.
主に方向別に検索し、zjydhrのコードを見て、現在の座標と前回の方向を与えるだけで、次のステップがどこまで行くかを計算することができ、遡及する必要はありませんが、実は1つのループで終わります.
 
3083
Accepted
220K
0MS
C++
1263B
2009-11-20 21:30:14
 

#include<stdio.h>
#include<queue>
using namespace std;
int m,n,l,r,f,sx,sy,d[2][4]={1,0,-1,0,0,1,0,-1};//     : , , , 
char t[41][41];
struct node
{int x,y,d;}ct;
int bfs(int x,int y)
{queue<node> q;
node st={x,y,1};
q.push(st);
while(!q.empty())
	{int i,tx,ty;
	ct=q.front();
	q.pop();
	for(i=0;i<4;i++)
		{tx=ct.x+d[0][i];
		ty=ct.y+d[1][i];
		if(tx>=0&&ty>=0&&tx<n&&ty<m&&t[tx][ty]!='#')
			{if(t[tx][ty]=='E')
				return ct.d+1;
			node ad={tx,ty,ct.d+1};
			t[tx][ty]='#';//         
			q.push(ad);
			}
		}
	}
	return 0;
}
int dfs(int x,int y,int z)//z    
{int i;
if(t[x][y]=='E')
	return 1;
for(i=0;i<4;i++)
	{int tx=x+d[0][z];
	int ty=y+d[1][z];
	if(t[tx][ty]=='.'||t[tx][ty]=='E')
		{
		if(f)//  
			{l++;
			if(z==3)
				z=-1;
			if(dfs(tx,ty,z+1))//   1,    
				return 1;;
			}
		else//  
			{r++;
			if(!z)
				z=4;
			if(dfs(tx,ty,z-1))//   1,    
				return 1;
			}
		}
	if(f)
		{z--;
		if(z==-1)
			z=3;
		}
	else
		{z++;
		if(z==4)
			z=0;
		}
	}
	return 0;
}
int main()
{int c,i,j;
scanf("%d",&c);
while(c--)
{scanf("%d%d",&m,&n);
for(i=0;i<n;i++	)
	{scanf("%s",t[i]);
	for(j=0;j<m;j++)
		if(t[i][j]=='S')
			{sx=i;
			sy=j;
			}
	}
	f=l=r=1;
	dfs(sx,sy,0);
	f=0;
	dfs(sx,sy,0);
	printf("%d %d %d/n",l,r,bfs(sx,sy));
}
}