首页 > 试题广场 >

走格子游戏

[编程题]走格子游戏
  • 热度指数：2574 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
G社正在开发一个新的战棋类游戏，在这个游戏中，角色只能向2个方向移动：右、下。移动需要消耗行动力，游戏地图上划分M*N个格子，当角色移动到某个格子上时，行动力就会加上格子上的值K（-100~100），当行动力<=0时游戏失败，请问要从地图左上角移动到地图右下角至少需要多少起始行动力，注意（玩家初始化到起始的左上角格子时也需要消耗行动力）

输入描述:
第一行输入格子行列数（格式为 M N），第2~M+1行每行输入N个数，作为格子值K，中间以空格分割；0 < M, N < 1000，-100 < K < 100


输出描述:
初始最小行动力
示例1

输入

2 3
-2 -3 3
-5 -10 1

输出

6
算法知识视频讲解
开通博客
头像 _Bingbong
发表于 2025-01-07 01:17:42
解题思路 这是一个动态规划问题，需要从终点反向计算到起点所需的最小行动力。关键是要保证路径上每个点的行动力都大于0。 关键点： 从终点反向计算 维护每个格子所需的最小行动力 考虑格子值为负数的情况 注意初始位置也需要消耗行动力 算法步骤： 创建dp数组，记录到达每个位置所需的最小行动力 从终点 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 iOS工程师 动态规划 安卓工程师 运维工程师 前端工程师 算法工程师 吉比特 2018 PHP工程师 查找 Java工程师
上传者：小小
难度：
14条回答 7563浏览

热门推荐

通过挑战的用户

查看代码

相关试题

走格子游戏

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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