首页 > ACM题库 > HDU-杭电 > HDU 1180 诡异的楼梯-优先队列-[解题报告] C++
2013
12-03

HDU 1180 诡异的楼梯-优先队列-[解题报告] C++

诡异的楼梯

问题描述 :

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

输入:

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

输出:

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

样例输入:

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

样例输出:

7
Hint

Hint

 
地图如下:

/*
思路就是广搜,碰到梯子原地等待,时间加一再入队(优先队列,时间少的队首),找到终点为止。
HDU 1180 诡异的楼梯
*/

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
#define CLR(c,v) (memset(c,v,sizeof(c)))

const int M = 25;
const int inf = 1 << 30;
const char road = '.';
const char t1 = '|';
const char t2 = '-';
const char start = 'S';
const char end = 'T';
const char obstacle = '*';
const char inqueue = '#';

char map[M][M];
int n,m;
int revise[][2] = {{-1,0},
		    	{0,-1},{0,1},
				   {1,0}};
struct _P{
	int x;int y;int minite;
	_P(int x = -1, int y = -1): x(x), y(y) {minite = 0;}
	bool operator < (const _P &a) const {
		return minite > a.minite;
	}
	bool operator == (const _P &a) const {
		return minite == a.minite;
	}
}S;

int BFS(){
	priority_queue <_P > que;
	que.push(S);
	while(!que.empty()){
 		_P now = que.top(); que.pop();
		if (end == map[now.x][now.y]){ // 终点
			return now.minite;
		}
		map[now.x][now.y] = obstacle;
		for (int i = 0; i < 4 ; i++){ // 四个方向
			int next_x = revise[i][0] + now.x;
			int next_y = revise[i][1] + now.y;
			if (next_x >= 0 && next_x < n && next_y >= 0 && next_y < m ){ // 没有出界
				if (map[next_x][next_y] == obstacle){
					continue;
				}else if (map[next_x][next_y] == road || map[next_x][next_y] == end ){ // 如果是路或终点
					_P next = _P(next_x , next_y);
					next.minite = now.minite + 1;
					(map[next_x][next_y] != end)?(map[next_x][next_y] = inqueue):(1);
					que.push(next);
				}else if ((map[next_x][next_y] == t1 || map[next_x][next_y] == t2 )&&  // 如果是梯子
						  ((map[revise[i][0]*2 + now.x][revise[i][1]*2 + now.y] != obstacle)  )){ // 并且梯子的另一边是路
					if (0 == i || 3 == i){ // 上下方向的梯子
						if (revise[i][0]*2 + now.x >= 0 && revise[i][0]*2 + now.x < n  ){// 没有出界
							if ((map[next_x][next_y] == t1 && (now.minite & 1) == 0) || 
								(map[next_x][next_y] == t2 && (now.minite & 1) == 1) ){
								// 梯子恰好能过去
								_P next = _P( revise[i][0]*2 + now.x , now.y);
								next.minite = now.minite + 1;
								//map[next_x][next_y] = obstacle;
								que.push(next);
							}else{  // 如果暂时不能过去
								_P next = _P( now.x , now.y);
								next.minite = now.minite + 1;
								que.push(next);
							}
						}
					}else if (1 == i || 2 == i ){ // 左右方向的梯子
						if (revise[i][1]*2 + now.y >= 0 && revise[i][1]*2 + now.y < m){// 没有出界
							if ((map[next_x][next_y] == t1 && (now.minite & 1) == 1) || 
								(map[next_x][next_y] == t2 && (now.minite & 1) == 0) ){
								// 梯子恰好能过去
								_P next = _P( now.x , revise[i][1]*2 + now.y);
								next.minite += now.minite + 1;
								//map[next_x][next_y] = obstacle;
								que.push(next);
							}else{	// 如果暂时不能过去
								_P next = _P( now.x ,  now.y);
								next.minite += now.minite + 1;
								que.push(next);
							}
						}
					}
				}
			}
		}
	}
	return 0;
}

int main(){
	//freopen("Input.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	while(scanf("%d %d",&n , &m) != EOF ){
		for (int i = 0; i < n ; i ++){
			scanf("%s",map[i]);
			for (int j = 0 ; j < m ; j++){
				if (start == map[i][j]){
					S = _P(i,j);
				}
			}
		}
 		printf("%d\n", BFS() );
	}
	return 0;
}

/*
一些变态的数据:
20 20
-.|...-............S
.-.|...-............
|.-.|...-...........
.|.-.|...-..........
..|.-.|...-.........
-..|.-.|...-........
.-..|.-.|...-.......
..-..|.-.|...-......
...-..|.-.|...-.....
....-..|.-.|...-....
.....-..|.-.|...-...
......-..|.-.|...-..
.......-..|.-.|...-.
........-..|.-.|...-
.........-..|.-.|...
..........-..|.-.|..
...........-..|.-.|.
............-..|.-.|
.............-..|.-.
T.............-..|.-
2 4
...T
S-..
3 4
.|S-
.*|.
T.*.
1 10
S-.|.-.-.T
1 1
T
20 1
S
-
.
-
.
-
.
-
.
-
.
-
.
-
.
-
.
-
.
T
1 2
ST
2 1
T
S
20 20
...................S
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
T...................
20 20
...................T
....................
|*******************
....................
*******************-
....................
|*******************
....................
*******************-
....................
|*******************
....................
*******************|
....................
-*******************
....................
*******************|
....................
-*******************
S...................
5 5
**..T
**.*.
**|..
**.**
S..**
5 5
.*..T
...*.
.-.*.
..|**
S-.**
5 5
.|.-T
-*-*|
.*.|.
-*-**
S|.**
5 5
S....
-|-|-
.....
-|-|-
....T
1 3
S-T
1 3
S|T
1 5
S|.|T
1 5
S-.-T
1 5
S|.-T
1 5
S-.|T
2 2
*T
S|
20 20
**.|.**.-.*|..-.*..T
.*|..-.*..**.-.|*..*
....|..|.|.-..-..|..
.-.**..*...-..-..*..
**.-.**..*-.-..*.*.|
.-...|.|...**..-.*..
.*|.-.-*.|.-.*-*.**.
-..*.*.*-.**.|.|*.*|
.-.*-..-...-..-..|..
-.-..*.**.|.*|.*..*-
.*|..-.*..**.-.|*..*
....|..|.|.-..-..|..
**.-.**..*-.-..*.*.|
.-.*-..-...-..-..|..
.-...|.|...**..-.*..
.*|.-.-*.|.-.*-*.**.
-..*.*.*-.**.|.|*.*|
.-.*-..-...-..-..|..
-.-..*.**.|.*|.*..*-
S|.*.*.|.-*.|.*.|.-.
10 20
**.|.**.-.*|..-.*..T
.*|..-.*..**.-.|*..*
....|..|.|.-..-..|..
**.-.**..*-.-..*.*.|
.-...|.|...**..-.*..
.*|.-.-*.|.-.*-*.**.
-..*.*.*-.**.|.|*.*|
.-.*-..-...-..-..|..
-.-..*.**.|.*|.*..*-
S|.*.*.|.-*.|.*.|.-.
4 9
-..-.-.|T
.*-*..*..
.*.*.***|
S-..*..*.
6 10
.|.*.|.*.T
****.-...*
***..-|*.*
-.**.***..
.-.|.*-*..
S.***-*.**

*/

 


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  2. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  3. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count