题意:小明因为受到大魔王的诅咒,被困到了一座荒无人烟的山上并无法脱离.这座山很奇怪:

这座山的底面是矩形的,而且矩形的每一小块都有一个特定的坐标(x,y)和一个高度H.

为了逃离这座山,小明必须找到大魔王,并消灭它以消除诅咒.

小明一开始有一个斗志值k,如果斗志为0则无法与大魔王战斗,也就意味着失败.

小明每一步都能从他现在的位置走到他的(N,E,S,W)(N,E,S,W)(N,E,S,W)四个位置中的一个,会消耗(abs(H​1​​−H​2​​))/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\n");

			continue;

		}

		BFS();

		if(ans < INF)

		    printf("%.2lf\n",ans);

		else

		    printf("No Answer\n");

	}

	return 0;

}