首页 > 试题广场 >

龙与地下城游戏问题

[编程题]龙与地下城游戏问题
  • 热度指数：391 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二维数组map，含义是一张地图，例如，如下矩阵

游戏的规则如下:
1）骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。
2）地图中每个位置的值代表骑士要遭遇的事情。如果是负数，说明此处有怪兽，要让骑士损失血量。如果是非负数，代表此处有血瓶，能让骑士回血。
3）骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于1。为了保证骑土能见到公主，初始血量至少是多少?
根据map,输出初始血量。

数据范围：矩阵的长宽都满足 ，矩阵中的值满足
示例1

输入

[[-2,-3,3],[-5,-10,1],[0,30,-5]]

输出

7
示例2

输入

[[1,1],[1,1]]

输出

1
算法知识视频讲解
添加回答
C
企鹅暴打皮卡丘头像 企鹅暴打皮卡丘
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param mp int整型二维数组 
 * @param mpRowLen int mp数组行数
 * @param mpColLen int* mp数组列数
 * @return int整型
 */
int max(int a,int b)
{
    if(a>b)
    return a;
    return b;
}
int min(int a,int b)
{
    if(a<b)
    return a;
    return b;
}
int dnd(int** mp, int mpRowLen, int* mpColLen ) {
    if(mpRowLen==0||*mpColLen==0)
        return 1;
    int dp[*mpColLen+2][mpRowLen+2];
    for(int i=0;i<mpRowLen;i++)
    {
        for(int j=0;j<*mpColLen;j++)
        dp[i][j]=1000000;
    }
    dp[mpRowLen][*mpColLen]= 1-mp[mpRowLen-1][*mpColLen-1];
    for(int i=mpRowLen-1;i>0;i--)
        {
            dp[i][*mpColLen]=dp[i+1][*mpColLen]-mp[i-1][*mpColLen-1];
        }
    for(int j=*mpColLen-1;j>0;j--)
        dp[mpRowLen][j]=dp[mpRowLen][j+1]-mp[mpRowLen-1][j-1];
    for(int i=mpRowLen-1;i>0;i--)
    {
        for(int j=*mpColLen-1;j>0;j--)
        dp[i][j]=max(min(dp[i][j+1],dp[i+1][j])-mp[i-1][j-1],1-mp[i-1][j-1]);
    }
    if(dp[1][1]<=0)
        dp[1][1]=1;
    return dp[1][1];
}
发表于 2022-09-27 16:38:29 回复(0)
提交观点

问题信息

动态规划
难度：
1条回答 1185浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号