CC

自然万物都趋向从有序变得无序

0%

诡异的楼梯 HDU - 1180

发表于 更新于 分类于 Valine：

题目链接:点我

题目

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

地图如下：
这里写图片描述

题意:

题目中文,说的已经很清晰了.

思路:

bfs,但是要考虑楼梯的方向,队友告诉我,可以在楼梯那里等(当时真是让我吃了一惊,不过好像也不无道理),于是此题就变简单了.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;

char w[30][30];
bool vis[30][30];
struct ss
{
    int x,y,time;
  friend  bool operator <(const ss &q,const ss &p)
    {
        return q.time>p.time;
    }
};
int n,m;
int sx,sy,px,py;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

bool judge(int x,int y)
{
    if(x>0&&y>0&&x<=n&&y<=m)
        return true;
    return false;
}
void bfs()
{
    priority_queue<ss> q;
    memset(vis,false,sizeof(vis));
    ss cur;
    cur.x=sx;
    cur.y=sy;
    cur.time=0;
    q.push(cur);
    vis[sx][sy]=true;
    while(!q.empty()){
        ss p=q.top();
        q.pop();
        if(p.x==px&&p.y==py){
            cout<<p.time<<endl;
            return ;
        }
        for(int i=0;i<4;++i){
            int x=p.x+dx[i];
            int y=p.y+dy[i];
            if(judge(x,y)&&vis[x][y]==false){
                if(w[x][y]=='.'){
                cur.x=x;
                cur.y=y;
                cur.time=p.time+1;
                q.push(cur);
                vis[x][y]=true;
                }else if(w[x][y]=='|'||w[x][y]=='-'){
                    x+=dx[i];
                    y+=dy[i];
                    if(judge(x,y)&&w[x][y]=='.'&&vis[x][y]==false){
                            cur.x=x;
                            cur.y=y;
                        if((i>1&&p.time%2==0&&w[x-dx[i]][y-dy[i]]=='|')||(w[x-dx[i]][y-dy[i]]=='-'&&i>1&&p.time%2==1)||(i<=1&&w[x-dx[i]][y-dy[i]]=='-'&&p.time%2==0)||(i<=1&&w[x-dx[i]][y-dy[i]]=='|'&&p.time%2==1)){
                        //这个判断语句有点丑,大家不要喷,主要是情况有点复杂
                          cur.time=p.time+1;
                        } else cur.time=p.time+2;
                            q.push(cur);
                        vis[x][y]=true;
                    }
                }
            }
        }
    }
}
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF){
        for(int i = 1;i <= n;++ i)
        for(int j = 1;j <= m;++ j){
            scanf(" %c",&w[i][j]);
            if(w[i][j]=='T'){
                w[i][j]='.';
                px=i,py=j;
            }
            if(w[i][j]=='S'){
                w[i][j]='.';
                sx=i,sy=j;
            }
        }  bfs();
    }
    return 0;
}