Time Limit: 1000MS | Memory Limit: 65536KB | 64bit IO Format: %I64d & %I64u |
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; }
0 条评论