题意:小明因为受到大魔王的诅咒,被困到了一座荒无人烟的山上并无法脱离.这座山很奇怪:
这座山的底面是矩形的,而且矩形的每一小块都有一个特定的坐标(x,y)和一个高度H.
为了逃离这座山,小明必须找到大魔王,并消灭它以消除诅咒.
小明一开始有一个斗志值k,如果斗志为0则无法与大魔王战斗,也就意味着失败.
小明每一步都能从他现在的位置走到他的(N,E,S,W)(N,E,S,W)(N,E,S,W)四个位置中的一个,会消耗(abs(H1−H2))/k的体力,每走一步消耗一点斗志。
大魔王很强大,为了留下尽可能多的体力对付大魔王,小明需要找到一条消耗体力最少的路径.
你能帮助小明算出最少需要消耗的体力吗.
思路 : BFS
代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
#define pii pair<int,int>
#define INF 0x7fffffff
struct node{
int x;
int y;
int k;
double cost;
};
double g[55][55],ans;
int sx,sy,ex,ey,n,m,k,flag;
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
char ch[55][55];
queue<node> Q;
void BFS(){
int i,x,y;
double temp;
node t ;
t.x = sx;
t.y = sy;
t.k = k;
t.cost = 0;
g[sx][sy] = 0;
Q.push(t);
while(!Q.empty()){
t = Q.front();
Q.pop();
if(t.x == ex && t.y == ey && t.k>=1){
flag = 1;
ans = ans < t.cost ? ans : t.cost;
continue;
}
if(t.k<=1)
continue;
for(i=0;i<4;i++){
x = t.x + dir[i][0];
y = t.y + dir[i][1];
if(x<=0 || x>n || y<=0 || y>m)
continue;
if(ch[x][y] == '#')
continue;
temp = t.cost + fabs((ch[x][y] - ch[t.x][t.y])*1.0/(t.k));
if(temp < g[x][y]){
Q.push((node){x,y,t.k-1,temp});
g[x][y] = temp;
}
}
}
}
int main(){
int i,j,T;
cin >> T;
while(T--){
ans = INF;
flag = 0;
while(!Q.empty())
Q.pop();
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
g[i][j] = INF;
for(i=1;i<=n;i++)
scanf("%s",ch[i]+1);
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
if(k <= 0 ){
printf("No Answer
");
continue;
}
BFS();
if(ans < INF)
printf("%.2lf
",ans);
else
printf("No Answer
");
}
return 0;
}