【搜索之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:
5696313	2012-04-03 14:44:43	Accepted	1180
0MS	280K	3502 B
C++	pyy


Test 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};

int		m, n;

char	map[MAXN][MAXN];
//bool	vis[MAXN][MAXN];

POINT	S, 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 = '-';
					else
						c = '|';
				}
				else
					c = _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;

				// 如果不判断楼梯背后的点是否被访问过，则会 MLE
				if (_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;
}