HDU 5433 Xiao Ming climbing dp

时间：2022-04-16 04:22:22

Xiao Ming climbing

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=629&pid=1002

Description

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

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

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

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

小明每一步都能从他现在的位置走到他的(N,E,S,W)(N,E,S,W)四个位置中的一个,会消耗(abs(H_1-H_2))/k(abs(H​1​​−H​2​​))/k的体力,然后消耗一点斗志。

大魔王很强大,为了留下尽可能多的体力对付大魔王,小明需要找到一条消耗体力最少的路径.

你能帮助小明算出最少需要消耗的体力吗.

Input

第一行输入一个整数T( 1 \leq T \leq 10 )T(1≤T≤10)

接下来有TT行TT组数据，每组数据有三个整数n,m,kn,m,k含义如题(1 \leq n,m \leq 50, 0 \leq k \leq 50)(1≤n,m≤50,0≤k≤50)

接下来有nn行,每行mm个字符,如果是数字则表示(i,j)(i,j)的高度H(0 \leq H \leq 9)H(0≤H≤9),'#'表示障碍

最后两行分别输入小明的坐标(x_1,y_1)(x​1​​,y​1​​)和大魔王的坐标(x_2,y_2)(x​2​​,y​2​​),小明和魔王都不在障碍上。

Output

每组数据对应输出满足要求的体力(保留两位小数)。

如果无法逃离,则输出"No \ AnswerNo Answer"

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

HINT

题意

题解：

dp咯，三维dp

dp[i][j][k]表示我现在在i,j位置体力值为k的最小花费是多少

用类似spfa一样转移就好了

代码：

//qscqesze

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <bitset>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 500001

#define mod 1001

#define eps 1e-7

#define pi 3.1415926

int Num;

//const int inf=0x7fffffff;

const ll inf=;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//*************************************************************************************

string s[];

int n,m;

int k;

double dp[][][];;

struct node

{

    int x,y,z;

};

int inq[][][];

int dx[]={,,-,};

int dy[]={,,,-};

int main()

{

    int t=read();

    while(t--)

    {

        memset(dp,,sizeof(dp));

        memset(inq,,sizeof(inq));

        n=read(),m=read();

        scanf("%d",&k);

        for(int i=;i<n;i++)

            cin>>s[i];

        int x1,y1,x2,y2;

        cin>>x1>>y1>>x2>>y2;

        if(x1==x2&&y1==y2)

        {

            if(k==)

                printf("No Answer\n");

            else

                printf("0.00\n");

            continue;

        }

        x1--,y1--,x2--,y2--;

        for(int i=;i<;i++)

        {

            for(int j=;j<;j++)

            {

                for(int k=;k<;k++)

                {

                    dp[i][j][k]=inf;

                }

            }

        }

        queue<node> Q;

        node ttt;

        ttt.x=x1,ttt.y=y1,ttt.z=k;

        Q.push(ttt);

        node now;

        now.x = x1,now.y = y1,now.z = k;

        dp[now.x][now.y][now.z]=;

        inq[now.x][now.y][now.z]=;

        while(!Q.empty())

        {

            now = Q.front();

            Q.pop();

            inq[now.x][now.y][now.z]=;

            for(int i=;i<;i++)

            {

                node next = now;

                next.x+=dx[i];

                next.y+=dy[i];

                next.z--;

                if(next.z==)

                    continue;

                if(next.x<||next.x>=n)

                    continue;

                if(next.y<||next.y>=m)

                    continue;

                if(s[next.x][next.y]=='#')

                    continue;

                double num1 = (int)(s[next.x][next.y]-'');

                double num2 = (int)(s[now.x][now.y]-'');

                double ss =  fabs(num1-num2)/now.z;

                if(dp[now.x][now.y][now.z]+ss<dp[next.x][next.y][next.z])

                {

                    dp[next.x][next.y][next.z]=dp[now.x][now.y][now.z]+ss;

                    if(!inq[next.x][next.y][next.z])

                    {

                        inq[next.x][next.y][next.z]=;

                        Q.push(next);

                    }

                }

            }

        }

        double ans = inf;

        for(int i=;i<;i++)

            ans = min(ans,dp[x2][y2][i]);

        if(ans == inf)

            printf("No Answer\n");

        else

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

    }

}

相关文章