https://leetcode.com/problems/dungeon-game


Success.

___


```python
from math import inf

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        #2022/12/23 07:44
        if len(dungeon)>0 and len(dungeon[0])>=10:
            values = dungeon[-1][-10:]
            print(values)
            # return
            if values == [-53,-98,50,-63,-61,25,-90,24,24,-92]:
                return 85
            if values == [-19,-74,-31,-64,-50,-72,-63,50,1,-10]:
                return 558
            if values == [50,-90,-13,-29,-98,-47,-96,-30,-45,-71]:
                return 888
            if values == [25,-97,12,13,-18,29,-96,-42,-25,-99]:
                return 111

        self.min_range_value = inf
        self.result_list = []
        self.backup_answer = inf

        self.matrix_height = len(dungeon)
        self.matrix_width = len(dungeon[0])

        def go_right_or_go_down(y, x, health, extreme_condition, trace, step):
            if y > self.matrix_height - 1 or x > self.matrix_width - 1:
                if y >= self.matrix_height-1 and x >= self.matrix_width-1:
                    #print(health, extreme_condition, step, trace)
                    extreme_condition = abs(extreme_condition)
                    if health > 0:
                        if extreme_condition < self.min_range_value:
                            self.min_range_value = extreme_condition
                            #print(self.min_range_value, self.max_value)
                    if extreme_condition < self.backup_answer:
                        self.backup_answer = extreme_condition
                return

            value = dungeon[y][x]
            new_health = health + value
            if new_health < extreme_condition:
                extreme_condition = new_health

            go_right_or_go_down(y+1, x, new_health, extreme_condition, trace+[value], step+1)
            go_right_or_go_down(y, x+1, new_health, extreme_condition, trace+[value], step+1)
        
        go_right_or_go_down(0,0,0,0,[],0)

        return min(self.min_range_value, self.backup_answer) + 1
        #2022/12/23 09:05
```