诡异的楼梯（HDOJ 1180）

Problem Description

Hogwarts正式开学以后,Harry发现在Hogwarts里,某些楼梯并不是静止不动的，相反,他们每隔一分钟就变动一次方向.
比如下面的例子里,一开始楼梯在竖直方向,一分钟以后它移动到了水平方向,再过一分钟它又回到了竖直方向.Harry发现对他来说很难找到能使得他最快到达目的地的路线,这时Ron(Harry最好的朋友)告诉Harry正好有一个魔法道具可以帮助他寻找这样的路线,而那个魔法道具上的咒语,正是由你纂写的.

Input

测试数据有多组，每组的表述如下：
第一行有两个数,M和N,接下来是一个M行N列的地图,'*'表示障碍物,'.'表示走廊,'|'或者'-'表示一个楼梯,并且标明了它在一开始时所处的位置:'|'表示的楼梯在最开始是竖直方向,'-'表示的楼梯在一开始是水平方向.地图中还有一个'S'是起点,'T'是目标,0<=M,N<=20,地图中不会出现两个相连的梯子.Harry每秒只能停留在'.'或'S'和'T'所标记的格子内.

Output

只有一行,包含一个数T,表示到达目标的最短时间.
注意:Harry只能每次走到相邻的格子而不能斜走,每移动一次恰好为一分钟,并且Harry登上楼梯并经过楼梯到达对面的整个过程只需要一分钟,Harry从来不在楼梯上停留.并且每次楼梯都恰好在Harry移动完毕以后才改变方向.

Sample Input

5 5
**..T
**.*.
..|..
.*.*.
S....

Sample Output

7

地图如下：

My Code

#include
#include
#include
using namespace std;
int n, m;
int dx[4] = { 0,1,0,-1 };			//dx和dy两个数组控制方向
int dy[4] = { 1,0,-1,0 };
char map[25][25];					//将迷宫的地图存下来
int v[25][25];						//标记走过的路
struct node
{
	int x, y;						//x和y是坐标
	int time;						//时间
}s;									//s是起始点
bool check(node p)
{
	if (p.x < 0 || p.y < 0)			//判断是否越界
		return false;
	if (p.x >= n || p.y >= m)
		return false;
	if (map[p.x][p.y] == '*')		//是否是障碍
		return false;
	if (v[p.x][p.y])				//是否走过
		return false;
	return true;
}
void bfs()
{
	queue q;
	q.push(s);						//将起始点入队
	node next, p;
	v[s.x][s.y] = 1;
	while (!q.empty())
	{
		p = q.front();				//队首是p
		q.pop();					//出队
		if (map[p.x][p.y] == 'T')			//到终点了，输出时间，退出
		{
			cout << p.time << endl;
			return;
		}
		//cout << p.x << ' ' << p.y << endl;
		for (int i = 0; i < 4; i++)
		{
			next.x = p.x + dx[i];	//计算下一个点next的坐标
			next.y = p.y + dy[i];
			//cout << next.x <<' '<< next.y<> n >> m)
	{
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
			{
				cin >> map[i][j];
				if (map[i][j] == 'S')
				{
					s.x = i;		//起始点初始化
					s.y = j;
					s.time = 0;
				}
			}
		memset(v, 0, sizeof(v));
		bfs();
	}
	return 0;
}