题意：给一张地图，给出起点和终点，每移动一步消耗体力abs(h1 - h2) / k的体力，k为当前斗志，然后消耗1斗志，要求到终点时斗志大于0，最少消耗多少体力。
解法：bfs。可以直接bfs，用dp维护最小值……也可以用优先队列优化……但是不能找到终点后就直接输出，因为从不同方向到达终点的消耗不同，终点的前一个状态不一定比这一状态更优……一开始并没有意识到这一点……wa了一篇……后来加了dp维护……但其实在将点弹出的之后再更新vis也可以……以前因为更新vis的问题T过……留下了阴影……
代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<limits.h>
#include<time.h>
#include<stdlib.h>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define LL long long
using namespace std;
char maze[55][55];
int sx, sy, ex, ey;
int n, m, k;
struct node
{
int x, y, k;
double tili;
bool operator < (const node &tmp) const
{
return tili > tmp.tili;
}
node(int x, int y, int k, double tili) : x(x), y(y), k(k), tili(tili) {}
node() {}
};
bool vis[55][55][55];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
double dp[55][55][55];
double bfs()
{
for(int i = 0; i < 55; i++)
for(int j = 0; j < 55; j++)
for(int k = 0; k < 55; k++)
dp[i][j][k] = 1e8;
memset(vis, 0, sizeof vis);
priority_queue <node> q;
q.push(node(sx, sy, k, 0.0));
vis[sx][sy][k] = 1;
while(!q.empty())
{
node tmp = q.top();
q.pop();
if(tmp.k == 0) continue;
if(tmp.x == ex && tmp.y == ey) return tmp.tili;
for(int i = 0; i < 4; i++)
{
int tx = tmp.x + dir[i][0], ty = tmp.y + dir[i][1];
if(tx < 0 || tx >= n || ty < 0 || ty >= m) continue;
if(maze[tx][ty] == '#') continue;
if(dp[tx][ty][tmp.k - 1] > (double)abs(maze[tx][ty] - maze[tmp.x][tmp.y]) / (double)tmp.k + tmp.tili)
{
dp[tx][ty][tmp.k - 1] = (double)abs(maze[tx][ty] - maze[tmp.x][tmp.y]) / (double)tmp.k + tmp.tili;
q.push(node(tx, ty, tmp.k - 1, (double)abs(maze[tx][ty] - maze[tmp.x][tmp.y]) / (double)tmp.k + tmp.tili));
}
}
}
return -1.0;
}
int main()
{
int T;
while(~scanf("%d", &T))
{
while(T--)
{
scanf("%d%d%d", &n, &m, &k);
for(int i = 0; i < n; i++)
scanf("%s", maze[i]);
scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
sx--;
sy--;
ex--;
ey--;
double ans = bfs();
if(ans < 0) puts("No Answer");
else printf("%.2f
", fabs(ans));
}
}
return 0;
}