学步园

Description

Input

Output

Sample Input

2
8 8
########
#......#
#.####.#
#.####.#
#.####.#
#.####.#
#...#..#
#S#E####
9 5
#########
#.#.#.#.#
S.......E
#.#.#.#.#
#########

Sample Output

37 5 5
17 17 9

题目大意:给定一个迷宫，S是起点，E是终点，#是墙不可走，.可以走。先输出贴左边墙走到E的步数，再输出贴

右边墙的，再输出最少走多少部能到E。。。

思路：这个是个综合题，BFS和DFS全用上了，代码快3KB了，我靠的，少考虑了一个情况，WA了许久，终于A了 我靠的。。。

8 8
########
#....#.#
#....#.#
#....#.#
#....#.#
#....#.#
S......#
#E######

少考虑了S转个弯就是E的情况。。WA了许久，终于发现这个BUG了。。。。汗。。

#include<iostream>
using namespace std;
char map[41][41],lock[41][41];	int head,rear,m,n,queue[2000];
struct mm
{
	int x,y;
}mm[4]={-1,0,0,1,1,0,0,-1};
void push(int i){queue[rear++%2000]=i;}
int pop(){return queue[head++%2000];}

int bfs()
{
	int x,y,step,i;
	while(head!=rear)
	{
		x=pop();	y=pop();	step=pop();
		if(map[x][y]=='E')	return step;
		for(i=0;i<4;i++)
			if(x+mm[i].x>-1&&x+mm[i].x<m&&y+mm[i].y>-1&&y+mm[i].y<n&&(map[x+mm[i].x][y+mm[i].y]=='.'||map[x+mm[i].x][y+mm[i].y]=='E')&&lock[x+mm[i].x][y+mm[i].y]==0)
			{	push(x+mm[i].x);	push(y+mm[i].y);	push(step+1);	lock[x+mm[i].x][y+mm[i].y]=1;	}
	}
	return 0;
}

int ldfs(int x,int y,int f)
{
	if(map[x][y]=='E')
		return 1;
	if((map[x+mm[f].x][y+mm[f].y]=='.'||map[x+mm[f].x][y+mm[f].y]=='E')&&map[x+mm[(f+3)%4].x][y+mm[(f+3)%4].y]=='#')
		return 1+ldfs(x+mm[f].x,y+mm[f].y,f);
	else
		if(!(map[x+mm[(f+3)%4].x][y+mm[(f+3)%4].y]=='#'))
		{
			return 1+ldfs(x+mm[(f+3)%4].x,y+mm[(f+3)%4].y,(f+3)%4);
		}
		else
			return ldfs(x,y,(f+1)%4);
}

int rdfs(int x,int y,int f)
{
	if(map[x][y]=='E')
		return 1;
	if((map[x+mm[f].x][y+mm[f].y]=='.'||map[x+mm[f].x][y+mm[f].y]=='E')&&map[x+mm[(f+1)%4].x][y+mm[(f+1)%4].y]=='#')
		return 1+rdfs(x+mm[f].x,y+mm[f].y,f);
	else
		if(!(map[x+mm[(f+1)%4].x][y+mm[(f+1)%4].y]=='#'))
		{
			return 1+rdfs(x+mm[(f+1)%4].x,y+mm[(f+1)%4].y,(f+1)%4);
		}
		else
			return rdfs(x,y,(f+3)%4);
}


int main()
{
	int t,i,j,x,y,f,o;
	cin>>t;
	while(t--)
	{
		memset(lock,0,sizeof(lock));
		head=rear=0;
		cin>>n>>m;
		for(i=0;i<m;i++)
			cin>>map[i];
		for(i=0;i<m;i++)
			for(j=0;j<n;j++)
				if(map[i][j]=='S')
					goto start;
		
start:	
		for(f=0;f<4;f++)
			if(i+mm[f].x>-1&&i+mm[f].x<m&&j+mm[f].y>-1&&j+mm[f].y<n&&(map[i+mm[f].x][j+mm[f].y]=='.'||map[i+mm[f].x][j+mm[f].y]=='E')&&map[i+mm[f].x+mm[(f+3)%4].x][j+mm[f].y+mm[(f+3)%4].y]=='#')
			{	o=1+ldfs(i+mm[f].x,j+mm[f].y,f);		break;		}
			else if(i+mm[f].x>-1&&i+mm[f].x<m&&j+mm[f].y>-1&&j+mm[f].y<n&&map[i+mm[f].x][j+mm[f].y]=='.'&&(map[i+mm[f].x+mm[(f+3)%4].x][j+mm[f].y+mm[(f+3)%4].y]=='.'||map[i+mm[f].x+mm[(f+3)%4].x][j+mm[f].y+mm[(f+3)%4].y]=='E'))
			{	o=2+ldfs(i+mm[f].x+mm[(f+3)%4].x,j+mm[f].y+mm[(f+3)%4].y,(f+3)%4);		break;		}

		cout<<o<<' ';
		for(f=0;f<4;f++)
			if(i+mm[f].x>-1&&i+mm[f].x<m&&j+mm[f].y>-1&&j+mm[f].y<n&&(map[i+mm[f].x][j+mm[f].y]=='.'||map[i+mm[f].x][j+mm[f].y]=='E')&&map[i+mm[f].x+mm[(f+1)%4].x][j+mm[f].y+mm[(f+1)%4].y]=='#')
			{	o=1+rdfs(i+mm[f].x,j+mm[f].y,f);		break;		}
			else if(i+mm[f].x>-1&&i+mm[f].x<m&&j+mm[f].y>-1&&j+mm[f].y<n&&map[i+mm[f].x][j+mm[f].y]=='.'&&(map[i+mm[f].x+mm[(f+1)%4].x][j+mm[f].y+mm[(f+1)%4].y]=='.'||map[i+mm[f].x+mm[(f+1)%4].x][j+mm[f].y+mm[(f+1)%4].y]=='E'))
			{	o=2+rdfs(i+mm[f].x+mm[(f+1)%4].x,j+mm[f].y+mm[(f+1)%4].y,(f+1)%4);		break;		}

		cout<<o<<' ';
		lock[i][j]=1;	push(i);	push(j);	push(1);
		cout<<bfs()<<endl;
	}

	return 0;
}