poj 3083dfs+bfs问题

题意：给你一个h * w的迷宫，其中有一句话需要注意一下“Exactly one 'S' and one 'E' will be present in the maze, and they will always be located along one of the maze edges and never in a corner.”即始点‘S’和终点‘E’一定都与迷宫的边界相邻，这对做题很关键。然后问你沿着迷宫墙壁的左边走和沿着迷宫墙壁的右边走，各需多少步，然后最少需要多少步。

 

思路：求最少步数没有什么好说当然是用bfs，重要的是求沿着迷宫墙壁走的两种状态。首先考虑，迷宫的起点是与墙壁挨着的，所以当S在迷宫最左边（sy == 0）如果沿着左边走，应该先考虑向上走的情况，如果向上走不通，在考虑像右走的情况，最后考虑向下走的情况；如果沿着右边走，应先考虑向下走的情况，再考虑向右走的情况，再考虑向上走的情况；其他的情况（sx == 0 || sy == w-1||sx == h - 1）时思路是一样的，自己推导吧~于是只要dfs枚举在每一个方向上可能有的各种情况就好了。又写了一遍这道题的代码 着道题我觉得重要的是方向的确立 与方向坐标的顺序 同时注意方向坐标 x，y分别表示的意思。 方向的确立的一种方法就是花一个正方形，若是右优先就是逆时针 ，把正方向的位子设为0 这个位置同时也是方向坐标(0,1)里面的位置，然后他的右边是1 既是上（1,0） 这样以此类推这种方向坐标位置的确立加方法无疑是这道题最精髓的东西。其实规定向左为顺时针或者逆时针是无所谓的，只要下次操作时与其一致就可以了，没必要那么纠结这个事情。 还要注意的事情就是当到底一个新的坐标的时候的时候，在这个新的坐标上也要考虑坐标移动的先后方向，按照以前设置好的方向进行考虑。
具体代码如下：

#include<iostream>
#include<queue>
using namespace std;
struct point
{
	int x,y;
	int step;
};
int flag[45][45];
char map[45][45];
int dir1[4][2]={{0,-1},{1,0},{0,1},{-1,0}};//zuo优先
int dir2[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//you优先
int d1,d2;
int start[2];
int end[2];
int w,h;
void init()
{
	memset(flag,0,sizeof(flag));
	cin>>w>>h; 
	for(int i=0;i<h;i++)
	{
		cin>>map[i];
		for(int j=0;j<w;j++)
		{
			if(map[i][j]=='#')
			{
				flag[i][j]=1;
			}
			if(map[i][j]=='S')
			{
				start[0]=i;
				start[1]=j;
			}
			if(map[i][j]=='E')
			{
				end[0]=i;
				end[1]=j;
			}
		}
	}
	if(start[0]==0)
	{
		d1=1;
		d2=1;
	}
	else if(start[0]==h-1)
	{
		d1=3;
		d2=3;
	}
	else if(start[1]==w-1)
	{
		d1=2;
		d2=0;
	}
	else
	{ 
		d1=0;
		d2=2;
	}
}
int dfs(int x,int y,int d,int dir[][2])
{
	int step ,temp, tempx,tempy;
	if(x==end[0]&&y==end[1])
		return 1;
	for(int i=0;i<4;i++)
	{
		temp=(d+i)%4;
		tempx=x+dir[temp][1];
		tempy=y+dir[temp][0];
		if(tempx>=0&&tempx<h&&tempy>=0&&tempy<w&&!flag[tempx][tempy])
			break;
	}
	step=dfs(tempx,tempy,(temp+3)%4,dir)+1;
	return step;
}


int bfs()
{
	memset(flag,0,sizeof(flag));
	queue<point> q;
	point p;
	p.x=start[0];
	p.y=start[1];
	p.step=1;
	flag[p.x][p.y]=1;
	q.push(p);
	while(!q.empty())
	{
		p=q.front();
		q.pop();
		if(p.x==end[0]&&p.y==end[1])
			return p.step;
		for(int i=0;i<4;i++)
		{
			point temp;
			temp.x=p.x+dir1[i][1];
			temp.y=p.y+dir1[i][0];
			if(temp.x>=0&&temp.x<h&&temp.y>=0&&temp.y<w&&map[temp.x][temp.y]!='#'&&!flag[temp.x][temp.y])
			{
				flag[temp.x][temp.y]=1;
				temp.step=p.step+1;
				q.push(temp);
			}
		}
	}
	return 0;
}




int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		init();
		cout<<dfs(start[0],start[1],d1,dir1)<<" ";
		cout<<dfs(start[0],start[1],d2,dir2)<<" ";
		cout<<bfs()<<endl;
	}
}