HDU 5433 Xiao Ming climbing

Problem Description

Due to the curse made by the devil,Xiao Ming is stranded on a mountain and can hardly escape.

This mountain is pretty strange that its underside is a rectangle which size is  n∗m and every little part has a special coordinate (x,y)and a height  H.

In order to escape from this mountain,Ming needs to find out the devil and beat it to clean up the curse.

At the biginning Xiao Ming has a fighting will  k,if it turned to  0 Xiao Ming won't be able to fight with the devil,that means failure.

Ming can go to next position (N,E,S,W)from his current position that time every step, (abs(H1−H2))/k 's physical power is spent,and then it cost  1 point of will.

Because of the devil's strong,Ming has to find a way cost least physical power to defeat the devil.

Can you help Xiao Ming to calculate the least physical power he need to consume.

Input

T(T≤10), indicating the number of testcases. 

Then  T testcases follow.

The first line contains three integers  n,m,k ,meaning as in the title (1≤n,m≤50,0≤k≤50).

Then the  N ×  M matrix follows.

In matrix , the integer  H meaning the height of  (i,j),and '#' meaning barrier (Xiao Ming can't come to this) .

Then follow two lines,meaning Xiao Ming's coordinate (x1,y1) and the devil's coordinate (x2,y2),coordinates is not a barrier.

Output

NoAnswer" otherwise.

(The result should be rounded to 2 decimal places)

Sample Input

3
4 4 5
2134
2#23
2#22
2221
1 1
3 3
4 4 7
2134
2#23
2#22
2221
1 1
3 3
4 4 50
2#34
2#23
2#22
2#21
1 1
3 3

Sample Output

1.03
0.00
No Answer

广搜

#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 105;
int T, n, m, k, bx, by, ex, ey;
int a[maxn][maxn];
int c[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1 };
double f[maxn][maxn][maxn];
char s[maxn];

struct point
{
    int x, y, z;
    point(){};
    point(int x, int y, int z) :x(x), y(y), z(z){};
};

void bfs()
{
    for (int i = 1; i <= n;i++)
        for (int j = 1; j <= m;j++)
            for (int u = 0; u <= k; u++) f[i][j][u] = 0x7FFFFFFF;
    queue<point> p;
    p.push(point(bx, by, 0));
    f[bx][by][0] = 0;
    while (!p.empty())
    {
        point q = p.front();    p.pop();
        if (q.z >= k) continue;
        for (int i = 0; i < 4; i++)
        {
            int x = q.x + c[i][0];
            int y = q.y + c[i][1];
            if (x<1 || x>n || y<1 || y>m || a[x][y] < 0) continue;
            double ans = 1.0*abs(a[x][y] - a[q.x][q.y]) / (k - q.z);
            if (f[x][y][q.z + 1]>f[q.x][q.y][q.z] + ans)
            {
                f[x][y][q.z + 1] = f[q.x][q.y][q.z] + ans;
                p.push(point(x, y, q.z + 1));
            }
        }
    }
    double ans = 0x7FFFFFFF;
    for (int i = k - 1; i >= 0; i--) ans = min(ans, f[ex][ey][i]);
    if (ans + 1e-5 < 0x7FFFFFFF) printf("%.2lf\n", ans);
    else printf("No Answer\n");
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= n; i++)
        {
            scanf("%s", s + 1);
            for (int j = 1; j <= m; j++) 
                if (s[j] == '#') a[i][j] = -1; else a[i][j] = s[j] - '0';
        }
        scanf("%d%d%d%d", &bx, &by, &ex, &ey);
        if (k) bfs(); else printf("No Answer\n");
    }
    return 0;
}