Dungeon Game

LeetCode Problem #174 (Hard)

Problem Statement

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.

Note:

• The knight's health has no upper bound.

• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Example

Consider the dungeon below:

Dungeon

The initial health of the knight must be at least 7 if he follows the optimal path:RIGHT-> RIGHT -> DOWN -> DOWN.

Input Format: Two-dimensional vector representing the dungeon.

Output Format: Integer representing the knight's minimum initial health.

Problem Explanation

By traversing through any square in the given grid, the knight may either gain health points or lose health points. Whether there is an increase in health points or decrease in health points is determined by the value within the grid cell. A positive value indicates that the knight would gain health points by travelling to that cell. A negative value indicates that the knight would lose health points by travelling to that cell.

In this problem, we must find the minimum possible value of the knight's initial health points such that their health value does not drop below 0 during their quest to find the princess.

In other words, we must find the number of health points that it would take to traverse from the starting point to the ending point if the optimal path is taken.

Prerequisite Knowledge

Dynamic Programming

Refer to the Prerequisite Knowledge section in Coin Change 2:

Coin Change 2

Algorithm

Bottom-Up DP Approach

In this approach, we traverse the grid from the bottom-right corner (destination) to the top-right corner (origin). In this solution, we do so by creating an auxiliary row and column in the bottom and right of the grid.

We must calculate the minimum possible health points required in order to enter a cell and if that value becomes less than 0, we must set the value to 1, since the knight needs at least 1 health point, to begin with.

1. Create a two-dimensional vector to store the value of health points, such that health[i][j] represents the health points required to enter the cell at position ( i, j).

2. Traverse through the grid in a bottom-up manner:

   a. Calculate the minimum number of health points required to travel to the next cell.

   b. If the health value drops below 0, reset the value to 1. Otherwise, calculate the maximum value required.

3. Return the resulting value generated in the origin cell as the initial health points possessed by the knight.

Time Complexity: O(m*n)

Code

int calculateMinimumHP(vector<vector<int>>& dungeon) {
    int rows = dungeon.size();
    int cols = dungeon[0].size();
    vector<vector<int>> health(rows + 1, vector<int>(cols + 1, INT_MAX));
    
    // health[i][j] = minimum health needed to enter position (i, j)
    // Create an auxiliary row and column on the bottom and right of the table respectively
    health[rows][cols - 1] = 1;
    health[rows - 1][cols] = 1;
    
    for(int i = rows - 1; i >= 0; i--) {
        for(int j = cols - 1; j >= 0; j--) {
            // Calculate the number of health points required to move to either possible cell.
            // Find the optimal path by choosing the minimum health value and deducting the value in the dungeon cell.
            int points = min(health[i + 1][j], health[i][j + 1]) - dungeon[i][j];
            // The knight would need at least 1 health point to begin with.
            // Choose the maximum value between the calculated points and the minimum possible points.
            health[i][j] = max(1, points);
        }
    }
    return health[0][0];
}