【搜索之BFS + 优先队列】杭电 hdu 1180 诡异的楼梯
?
/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------// Copyright (c) 2012 panyanyany All rights reserved. URL : http://acm.hdu.edu.cn/showproblem.php?pid=1180 Name : 1180 诡异的楼梯 Date : Tuesday, April 03, 2012 Time Stage : 3 hours Result:56963132012-04-03 14:44:43Accepted11800MS280K3502 BC++pyyTest Data :Review :WA了无数次之后，看到有人说用优先队列……于是AC了，但不明白有人没用优先队列是怎么AC的，求解答！//----------------------------------------*/#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#include <vector>#include <algorithm>#include <iostream>#include <queue>using namespace std ;#define MEM(a, v) memset (a, v, sizeof (a)) // a for address, v for value#define max(x, y) ((x) > (y) ? (x) : (y))#define min(x, y) ((x) < (y) ? (x) : (y))#define INF (0x3f3f3f3f)#define MAXN (22)#define DB /##/#define LL __int64#define _IN_RANGE(a, s, t)((s) <= (a) && (a) < (t))#define _IN(x, y)(_IN_RANGE(x, 0, m) && _IN_RANGE(y, 0, n))#define _MAP(pt)map[pt.x][pt.y]struct POINT {POINT(int ax = -1, int ay = -1): x(ax), y(ay) {}bool operator== (const POINT &pt) const {return pt.x == x && pt.y == y;}bool operator< (const POINT &pt) const {// 两个 const 的限定是必须的，否则会报错return mi > pt.mi;}int x, y;int mi;} path[MAXN][MAXN];const int dir[4][2] = {0,1, 0,-1, 1,0, -1,0};intm, n;charmap[MAXN][MAXN];//boolvis[MAXN][MAXN];POINTS, T, np, tm;int bfs(){char c ;int i, j;priority_queue<POINT>q; // 因为有楼梯的存在，所以每个格子的花费不是完全相同// 因此要用到优先队列// 要注意 m = n = 0 的情况S.mi = 0;T.mi = 0;path[T.x][T.y] = T;q.push(S);while (!q.empty()){tm = q.top();path[tm.x][tm.y] = tm;q.pop();if (tm == T)break;DB printf("\ntm:(%d,%d), map:%c, mi:%d\n", tm.x, tm.y, _MAP(tm), tm.mi);DB printf("---- for ----\n");for (i = 0; i < 4; ++i){np = tm;np.x = np.x + dir[i][0];np.y = np.y + dir[i][1];if (!_IN(np.x, np.y) || '*' == _MAP(np))continue;DB printf("1. np: (%d,%d), map:%c, mi:%d\n", np.x, np.y, _MAP(np), np.mi);if ('.' == _MAP(np)){np.mi = tm.mi + 1;_MAP(np) = '*';q.push(np);}else{if (tm.mi & 1)// 时间为奇数，则楼梯转向{if ('|' == _MAP(np))c = '-';elsec = '|';}elsec = _MAP(np);// 楼梯与自己的方向不同，则等一分钟，并使楼梯转向if ('|' == c && np.y != tm.y){c = '-';np.mi = tm.mi + 1;}else if ('-' == c && np.x != tm.x){c = '|';np.mi = tm.mi + 1;}// 把harry送到对面if ('|' == c){if (np.x < tm.x)// 向上送--np.x;else if (np.x > tm.x)// 向下送++np.x;}else{if (np.y < tm.y)// 向左边送--np.y;else if (np.y > tm.y)// 向右边送++np.y;}// 送的过程要一分钟++np.mi;// 如果不判断楼梯背后的点是否被访问过，则会 MLEif (_IN(np.x, np.y) && '*' != _MAP(np))q.push(np);}DB printf("2. np: (%d,%d), map:%c, mi:%d\n", np.x, np.y, _MAP(np), np.mi);}}return path[T.x][T.y].mi;}int main(){int i, j;while (scanf("%d %d", &m, &n) != EOF){for (i = 0; i < m; ++i){getchar();for (j = 0; j < n; ++j){scanf("%c", &map[i][j]);if (map[i][j] == 'S'){S = POINT(i, j);map[i][j] = '*';// 起点没有用了，标记为墙}else if ('T' == map[i][j]){T = POINT(i, j);map[i][j] = '.';// 终点标记为走廊，方便bfs统一处理}}}printf ("%d\n", bfs());}return 0;}?