题目描述
小未在玩一款武侠游戏，游戏里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
****************************************************************/