HDU 1180 诡异的楼梯 解题报告

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

Hint

Hint

地图如下：

Source

Gardon-DYGG Contest 1

思路：BFS+优先队列（小顶堆）。根据当前步数的奇偶性判断楼梯的方向，如果楼梯不能走就把当前步数+1入队。

AC代码：

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int m, n;
char map[25][25];
bool vis[25][25];
const int dx[] = {0, 0, 1, -1},
			dy[] = {1, -1, 0, 0};
struct node
{
	int x, y, step;
	bool operator < (const node b) const
	{
		return step > b.step;
	}
};
node start, goal;
priority_queue <node> q;
void input()
{
	for (int i = 0; i < m; i++)
		scanf("%s", map[i]);
}
void pre()
{
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
		{
			if (map[i][j] == 'S')
				start = (node){i, j, 0};
			else if (map[i][j] == 'T')
				goal = (node){i, j, 0};
		}
	while (!q.empty())
		q.pop();
	memset(vis, 0, sizeof(vis));
}
bool check(int x, int y)
{
	if (x < 0 || x >= m || y < 0 || y >= n || vis[x][y] || map[x][y] == '*')
		return 0;
	return 1;
}
void bfs()
{
	pre();
	vis[start.x][start.y] = 1;
	q.push(start);
	while (!q.empty())
	{
		node u = q.top();
		q.pop();
		if (u.x == goal.x && u.y == goal.y)
		{
			printf("%d\n", u.step);
			return;
		}
		node next;
		for (int i = 0; i < 4; i++)
		{
			next.x = u.x + dx[i];
			next.y = u.y + dy[i];
			if (!check(next.x, next.y))
				continue;
			if (map[next.x][next.y] == '-' || map[next.x][next.y] == '|')
			{
				int curmap = 0;
				if (map[next.x][next.y] == '|')
					curmap = 1;
				if (u.step % 2)
					curmap = !curmap;
				if ((!curmap && (i == 2 || i == 3)) || (curmap && (i == 0 || i == 1)))
				{
					next = u;
					next.step++;
					q.push(next);
					continue;
				}
				next.x += dx[i];
				next.y += dy[i];
				if (!check(next.x, next.y))
					continue;
			}
			vis[next.x][next.y] = 1;
			next.step = u.step + 1;
			q.push(next);
		}
	}
}
int main()
{
	while (scanf("%d%d", &m, &n) == 2)
	{
		input();
		bfs();
	}
	return 0;
}