#include<stdio.h>
#include<queue>
using namespace std;
char map[45][45];
int ii,jj,ans,si,sj,ei,ej;
int get(int i,int j)
{
	if(i==0)
		return 3;
	if(i==(ii-1))
		return 1;
	if(j==0)
		return 2;
	return 4;
}
int ok(int nowi,int nowj)
{
	if(nowi<0||nowi>=ii||nowj<0||nowj>=jj)
		return 0;
	return 1;
}
void dfs(int nowi,int nowj,int d)
{
	if(!ok(nowi,nowj)||(si==nowi&&sj==nowj&&ans!=0))
		return ;
	ans++;
	if(nowi==ei&&nowj==ej)
		return ;
	if(d==1)
	{
		if(ok(nowi,nowj-1)&&map[nowi][nowj-1]=='.')//face 1
			dfs(nowi,nowj-1,4);
		else if(ok(nowi-1,nowj)&&map[nowi-1][nowj]=='.')
			dfs(nowi-1,nowj,1);
		else if(ok(nowi,nowj+1)&&map[nowi][nowj+1]=='.')
			dfs(nowi,nowj+1,2);
		else if(ok(nowi+1,nowj)&&map[nowi+1][nowj]=='.')
			dfs(nowi+1,nowj,3);
	}
	if(d==2)
	{
		if(ok(nowi-1,nowj)&&map[nowi-1][nowj]=='.')
			dfs(nowi-1,nowj,1);
		else if(ok(nowi,nowj+1)&&map[nowi][nowj+1]=='.')
			dfs(nowi,nowj+1,2);
		else if(ok(nowi+1,nowj)&&map[nowi+1][nowj]=='.')
			dfs(nowi+1,nowj,3);
		else if(ok(nowi,nowj-1)&&map[nowi][nowj-1]=='.')//face 1
			dfs(nowi,nowj-1,4);
	}
	if(d==3)
	{
		if(ok(nowi,nowj+1)&&map[nowi][nowj+1]=='.')
			dfs(nowi,nowj+1,2);
		else if(ok(nowi+1,nowj)&&map[nowi+1][nowj]=='.')
			dfs(nowi+1,nowj,3);
		else if(ok(nowi,nowj-1)&&map[nowi][nowj-1]=='.')//face 1
			dfs(nowi,nowj-1,4);
		else if(ok(nowi-1,nowj)&&map[nowi-1][nowj]=='.')
			dfs(nowi-1,nowj,1);
	}
	if(d==4)
	{
		if(ok(nowi+1,nowj)&&map[nowi+1][nowj]=='.')
			dfs(nowi+1,nowj,3);
		else if(ok(nowi,nowj-1)&&map[nowi][nowj-1]=='.')//face 1
			dfs(nowi,nowj-1,4);
		else if(ok(nowi-1,nowj)&&map[nowi-1][nowj]=='.')
			dfs(nowi-1,nowj,1);
		else if(ok(nowi,nowj+1)&&map[nowi][nowj+1]=='.')
			dfs(nowi,nowj+1,2);
	}
	return ;
}
void dfs1(int nowi,int nowj,int d)
{
	if(!ok(nowi,nowj)||(si==nowi&&sj==nowj&&ans!=0))
		return ;
	ans++;
	if(nowi==ei&&nowj==ej)
		return ;
	if(d==1)
	{
		if(ok(nowi,nowj+1)&&map[nowi][nowj+1]=='.')
			dfs1(nowi,nowj+1,2);
		else if(ok(nowi-1,nowj)&&map[nowi-1][nowj]=='.')
			dfs1(nowi-1,nowj,1);
		else if(ok(nowi,nowj-1)&&map[nowi][nowj-1]=='.')//face 1
			dfs1(nowi,nowj-1,4);
		else if(ok(nowi+1,nowj)&&map[nowi+1][nowj]=='.')
			dfs1(nowi+1,nowj,3);	
	}
	if(d==2)
	{
		if(ok(nowi+1,nowj)&&map[nowi+1][nowj]=='.')
			dfs1(nowi+1,nowj,3);	
		else if(ok(nowi,nowj+1)&&map[nowi][nowj+1]=='.')
			dfs1(nowi,nowj+1,2);
		else if(ok(nowi-1,nowj)&&map[nowi-1][nowj]=='.')
			dfs1(nowi-1,nowj,1);
		else if(ok(nowi,nowj-1)&&map[nowi][nowj-1]=='.')//face 1
			dfs1(nowi,nowj-1,4);		
	}
	if(d==3)
	{
		if(ok(nowi,nowj-1)&&map[nowi][nowj-1]=='.')//face 1
			dfs1(nowi,nowj-1,4);
		else if(ok(nowi+1,nowj)&&map[nowi+1][nowj]=='.')
			dfs1(nowi+1,nowj,3);	
		else if(ok(nowi,nowj+1)&&map[nowi][nowj+1]=='.')
			dfs1(nowi,nowj+1,2);
		else if(ok(nowi-1,nowj)&&map[nowi-1][nowj]=='.')
			dfs1(nowi-1,nowj,1);			
	}
	if(d==4)
	{
		if(ok(nowi-1,nowj)&&map[nowi-1][nowj]=='.')
			dfs1(nowi-1,nowj,1);
		else if(ok(nowi,nowj-1)&&map[nowi][nowj-1]=='.')//face 1
			dfs1(nowi,nowj-1,4);
		else if(ok(nowi+1,nowj)&&map[nowi+1][nowj]=='.')
			dfs1(nowi+1,nowj,3);	
		else if(ok(nowi,nowj+1)&&map[nowi][nowj+1]=='.')
			dfs1(nowi,nowj+1,2);				
	}
}
int movei[4]={-1,0,1,0};
int movej[4]={0,1,0,-1};
void bfs(int nowi,int nowj)
{
	queue<int> i;
	queue<int> j;
	int p,num=0,end=1;;
	i.push(nowi);
	j.push(nowj);
	while(true)
	{
		ans++;
		p=0;
		while(p<end)
		{
			nowi=i.front();
			nowj=j.front();
			i.pop();
			j.pop();
			for(int t=0;t<4;t++)
			{
				int iii=nowi+movei[t];
				int jjj=nowj+movej[t];
				if(ok(iii,jjj)&&map[iii][jjj]=='.')
				{
					if(iii==ei&&jjj==ej)
						goto tt;
					i.push(iii);
					j.push(jjj);
					num++;
				}
			}
			map[nowi][nowj]='#';
			p++;
		}
		end=num;
		num=0;
	}
	tt:;
	ans++;
}
int main()
{
	int ncase,i,j;
	scanf("%d",&ncase);
	while(ncase--)
	{
		scanf("%d%d",&jj,&ii);
		for(i=0;i<ii;i++)
		{
			scanf("%s",map[i]);
			for(j=0;j<jj;j++)
			{
				if(map[i][j]=='S')
				{
					si=i;
					sj=j;
				}
				if(map[i][j]=='E')
				{
					ei=i;
					ej=j;
					map[i][j]='.';
				}
			}
		}
		ans=0;
		dfs(si,sj,get(si,sj));
		printf("%d ",ans);
		ans=0;
		dfs1(si,sj,get(si,sj));
		printf("%d ",ans);
		ans=0;
		bfs(si,sj);
		printf("%d\n",ans);
	}
	return 0;
}

• 我也是TLE 想不通 40*40*2*case 咋就会超时呢？ (0) lychee 2008-10-29 22:39:42