4795498_ac_0ms_316k.cpp

部分PKU上的源码

#include<iostream>
#define le true
#define ri false
#define N 0
#define E 1
#define S 2
#define W 3
using namespace std;
char map[42][42];
bool used[42][42];
struct point
{
	int x,y,step;
}q[10000];
int xm[4]={-1,0,1,0};
int ym[4]={0,1,0,-1};
int w,h;
int sx,sy,ex,ey;
int get_bd(int x,int y)
{
	if(x==0) return S;
	else if(x==h-1) return N;
	else if(y==0) return E;
	else return W;
}
bool dfs(int x,int y,int dir,bool turn,int step)
{
	if(x==ex&&y==ey) {cout<<step<<" ";return true;}
	if(turn==le)
	{
		for(int count=-1;count<3;count++)
		{
			int temp=dir+count;
			temp%=4;
			if(temp<0) temp+=4;
			if(x+xm[temp]>=0&&x+xm[temp]<=h-1&&y+ym[temp]>=0&&y+ym[temp]<=w-1)
			{
				if(map[x+xm[temp]][y+ym[temp]]!='#')
				{
					return dfs(x+xm[temp],y+ym[temp],temp,turn,step+1);
				}
			}
		}
	}
	else
	{
		for(int count=1;count>-3;count--)
		{
			int temp=dir+count;
			temp%=4;
			if(temp<0) temp+=4;
			if(x+xm[temp]>=0&&x+xm[temp]<=h-1&&y+ym[temp]>=0&&y+ym[temp]<=w-1)
			{
				if(map[x+xm[temp]][y+ym[temp]]!='#')
				{
					return dfs(x+xm[temp],y+ym[temp],temp,turn,step+1);
				}
			}
		}
	}
	return false;
}
bool bfs()
{
	int ql=0;
	q[0].x=sx;q[0].y=sy;q[0].step=1;
	int head,tail;
	head=0;tail=1;
	memset(used,false,sizeof(used));
	while(head<tail)
	{
		point t=q[head];
		for(int count=0;count<4;count++)
		{
			if(t.x+xm[count]>=0&&t.x+xm[count]<=h-1&&t.y+ym[count]>=0&&t.y+ym[count]<=w-1)
			{
				if(map[t.x+xm[count]][t.y+ym[count]]=='E') {cout<<t.step+1;return true;;}
				else 
				if(map[t.x+xm[count]][t.y+ym[count]]=='.')
				{
					if(used[t.x+xm[count]][t.y+ym[count]]==false)
					{
						q[tail].x=t.x+xm[count];
						q[tail].y=t.y+ym[count];
						q[tail].step=t.step+1;
						used[t.x+xm[count]][t.y+ym[count]]=true;
						tail++;
					}
				}
			}
		}
		head++;
	}
	return false;
}
int main()
{
	int testnumber;
	cin>>testnumber;
	for(int i=0;i<testnumber;i++)
	{
		cin>>w>>h;
		int j;
		for(j=0;j<h;j++) 
		{
			scanf("%s",map[j]);
			int k=0;
			while(map[j][k]) 
			{
				switch(map[j][k])
				{
				case 'S':sx=j;sy=k;break;
				case 'E':ex=j;ey=k;break;
				}
				k++;
			}
		}
		int bdir=get_bd(sx,sy);
		dfs(sx,sy,bdir,le,1);
		dfs(sx,sy,bdir,ri,1);
		bfs();
		cout<<endl;
	}
	return 0;
}