首页 > 试题广场 >

龙与地下城游戏问题

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

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


输入描述:
第一行两个正整数n,m  ,接下来n行,每行m个整数,代表


输出描述:
输出一个整数,表示答案。
示例1

输入

3 3
-2 -3 3
-5 -10 1
0 30 -5

输出

7
示例2

输入

2 2
1 1
1 1

输出

1

备注:
时间复杂度,额外空间复杂度

这道题你会答吗?花几分钟告诉大家答案吧!