首页 > 代码库 > BDFZOI bdfz历险记

BDFZOI bdfz历险记

难度:提高-

题目类型:BFS

提交次数:2

涉及知识:BFS

描述

公主又又又被大魔王抓走啦!这次公主被困在一个叫做“bdfz”的迷宫里,作为勇者的你必须穿越这个迷宫才能找到公主。在迷宫中除了有道路和墙壁,你还会遇到各种各样的事件,影响你的血量,并且同一事件可以反复触发,例如:

‘1’:起太晚上学迟到,血量-1

‘2’:考太差惨遭嘲讽,血量-2

‘5’:上课睡着没听课,血量-5

‘X’:导师约谈,血量+1

‘Y’:幡然悔悟,血量+5

假设进入迷宫时你的起始血量为L,每移动1个位置需要1单位时间,若血量减至<=0,则需要原地回血直到血量为正值,1单位时间可以回复1点血量。血量上限为100(即血量不会超过100)。

输入第一行3个整数N,M,L(N,M,L<=50)
随后N行,每行有M个字符。字符的意义如下:
‘.’:道路
‘a’:公主
‘@’:勇者起始位置
‘#’:墙壁
‘1’:起太晚上学迟到,血量-1
‘2’:考太差惨遭嘲讽,血量-2
‘5’:上课睡着没听课,血量-5
‘X’:导师约谈,血量+1
‘Y’:翻然悔悟,血量+5输出如果能救出公主,输出最短时间;否则输出"Impossible"样例输入

样例1:
6 8 2
....Y...
..@..#2.
.##.51..
.X#.#...
...X51..
...##a..

样例2:
6 8 2
YYY##...
Y.@55#2.
####55#.
.X#.#5#.
...Y55#.
...##a..

样例输出

样例1:
10

样例2:
15

代码:
 1 #include<iostream>
 2 #include<cstring>
 3 #include<queue>
 4 #include<cstdio>
 5 using namespace std;
 6 int n, m, l;
 7 char map[60][60];
 8 bool visited[60][60][60];
 9 int dirx[4]={1,-1,0,0};
10 int diry[4]={0,0,1,-1};
11 
12 struct node{
13     int x, y;
14     int time, blood;
15     node(int xx, int yy, int tt, int bb): x(xx),y(yy),time(tt),blood(bb){}
16 };
17 
18 bool operator<(const node&n1, const node&n2){
19     return n1.time>n2.time;
20 }
21 
22 bool judge(int x, int y){
23     if(map[x][y]!=# && map[x][y]!= 0)
24         return true;
25     else 
26         return false;
27 }
28 int chb(char a){
29     if(a==.||a==@||a==a) return 0;
30     if(a==X) return 1;
31     if(a==Y) return 5;
32     else return -(a-0);
33 }
34 priority_queue<node>pq;
35 
36 int main(){
37     cin>>n>>m>>l;
38     int i, j;
39     memset(visited,0,sizeof(visited));
40     for(i = 1; i <= n; i++)
41         for(j = 1; j <= m; j++){
42             cin>>map[i][j];
43             if(map[i][j]==@){
44                 pq.push(node(i,j,0,l));
45                 visited[i][j][l] = true;
46             }    
47         }
48         
49     bool flag = false;
50     while(!pq.empty()){
51         node no = pq.top();
52         pq.pop();
53 //        cout<<no.x<<" "<<no.y<<" "<<no.blood<<" "<<no.time<<":"<<endl;
54         if(map[no.x][no.y]==a){
55             cout<<no.time<<endl;
56             flag = true;
57             break;
58         }
59         
60         else{
61             for(i = 0; i < 4; i++){
62                 int nx = no.x+dirx[i];
63                 int ny = no.y+diry[i];
64                 int nb = no.blood + chb(map[nx][ny]);
65                 int deltatime = 0;
66                 if(nb <= 0){
67                     deltatime = 0-nb+1;
68                     nb = 1;
69                 }
70     //            cout<<visited[nx][ny][nb]<<" "<<judge(nx,ny)<<endl;
71                 
72                 if(!visited[nx][ny][nb]&&judge(nx,ny)){
73         //            cout<<nx<<" "<<ny<<" "<<nb<<" "<<no.time+1+deltatime<<endl;
74                     pq.push(node(nx,ny,no.time+deltatime+1,nb));
75                     visited[nx][ny][nb] = true;
76                 }
77             }
78         }
79     //    getchar();
80     }
81     if(!flag) cout<<"Impossible"<<endl;
82     return 0;
83 } 

备注:

多维BFS,加一个关于血量的参数。没血之后要花时间(deltatime)原地回血。chb函数是change the blood,这个函数里没有把所有地形都定义全(终点血量乱了),导致查了一个小时的错误。。

第二个错误是没写deltatime,直接把正在扩展的no.time给改了,这样肯定就不对了。。

BDFZOI bdfz历险记