Company: Quince_13nov
Difficulty: medium
Dungeon Game The wicked witch has captured the prince and imprisoned him in the bottom-right corner of a dungeon. The dungeon is a grid of m x n rooms. The knight starts in the top-left room and must fight her way through to rescue him. The knight carries a health level, a positive integer. Entering a room immediately changes her health by the value written in that room: a negative value is a goblin, and she loses that much health; a zero is an empty room and leaves her health unchanged; a positive value is a magic potion, and she gains that much health. If her health ever drops to 0 or below, she dies immediately. To reach the prince as quickly as possible she moves only right or down at each step. Any room may hold goblins or a potion, including the top-left room she starts in and the bottom-right room where the prince is held. The value of the starting room is applied the moment she enters it, before she takes any step. Determine the smallest initial health the knight can start with