2849: 【广度优先】【优先队列】游戏装备

题目描述

小未在玩一款武侠游戏，游戏里PK不仅要有高超的操作和智慧，还要有很牛的装备。现在他进入了一个副本，副本里面有极品15星的装备宝箱，但是从副本入口到宝箱有很多条路，当然不可能轻轻松松的拿到极品装备。一路上会随机刷出各种攻击力很强的怪物。它会攻击小未的角色，当然也必须打败它才能通过，这个过程角色的血量HP会减少(血量不会回复)，预先给你副本的地图，请你帮小未计算一下能不能拿到极品装备。

注意：刚进入副本时角色是满血的，中途没有任何回血的措施，在过程中血量hp必需>0,不然副本结束(即拿不到极品装备)。

输入

输入一共有 n+k+2 行，
第一行依次为 n, m, k, H，分别表示副本行列数，怪物数，角色的满血血量。其中 n≤100，m≤100, k≤10, H≤200。
第二行四个整数，表示副本入口坐标和宝箱所在坐标。数据保证起点和终点所在的格子都是 空的。
接下来 n 行，每行一个长度为 m 的字符串，表示副本地图。‘.’表示可走，#表 示为不可走，A-Z 的字符表示怪物种类
接下来 k 行
接下来的第 1 行，一个数表示 A 怪物会使角色扣多少血；
接下来的第 2 行，一个数表示 B 怪物会使角色扣多少血；
……
接下来的第 k 行...
以此类推，扣的血量小于等于 200。

输出

输出共一行，表示到达终点最后最多剩下多少血。如果不能拿到装备，则输出game over

样例输入

5 5 2 15
1 1 5 4
....A
####.
.....
###B#
.....
9
3

样例输出

3

Code:

#include<bits/stdc++.h>
using namespace std;
char mp[205][205];
int n,m,k,h;
int ax,ay,bx,by;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int a[250];
struct love{
    int x,y;
    int xueliang;
    friend bool operator < (love a,love b){
        return a.xueliang<b.xueliang;
    }
};
int bfs(int nx,int ny,int step){
    priority_queue <love> q;
    love first,next;
    first.x=nx;
    first.y=ny;
    first.xueliang=step;
    q.push(first);
    while(!q.empty()){
        first=q.top();
        q.pop();
        for(int i=0;i<4;i++){
            int fx=first.x+dx[i];
            int fy=first.y+dy[i];
            if(fx==bx&&fy==by){
                return first.xueliang;
            }
            if(fx>=1&&fx<=n&&fy>=1&&fy<=m&&mp[fx][fy]!='#'){
                if(mp[fx][fy]>='A'&&mp[fx][fy]<='Z'){
                    next.xueliang=first.xueliang-a[mp[fx][fy]-'A'];
                }else{
                    next.xueliang=first.xueliang;
                }
                next.x=fx;
                next.y=fy;
                mp[next.x][next.y]='#';
                q.push(next);
            }
        }
    }
    return -1;
}
int main(){
    cin>>n>>m>>k>>h;
    cin>>ax>>ay>>bx>>by;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
        }
    }
    for(int i=0;i<k;i++){
        cin>>a[i];
    }
    int ans=bfs(ax,ay,h);
    if(ans<=0){
        cout<<"game over";
    }else{
        cout<<ans;
    }
    return 0;
}
/**************************************************************
    Problem: 2849
    User: yangrenrui
    Language: C++
    Result: 正确
    Time:20 ms
    Memory:2232 kb
****************************************************************/