"Dungeon Game" solution

Question

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.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

Notes:

• 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.

I was tackling this problem and I ended up with code that is functional, but times out with really large input (meaning it's poorly optimized). I'm a beginner in programming and working out a functional algorithm was extremely hard for me. Now that I have to optimize it, I don't even know how to start.

Is there a way to optimize this code that doesn't change the fundamental underlying logic or is the approach I took doomed to be inefficient? If there is a way to optimize this, could you please provide some examples?

class Solution {
public:
int calculateMinimumHP(vector< vector<int> > &dungeon) {
    return 1 - actualFunction(dungeon, 0, 0, 0);
}
int actualFunction(vector< vector<int> > &dungeon, int roomCoordX, int roomCoordY, int shield){
    if(dungeon.size() == roomCoordX + 1 && dungeon[0].size() == roomCoordY + 1){
        if(shield + dungeon[roomCoordX][roomCoordY] < 0)
            return (dungeon[roomCoordX][roomCoordY] + shield);
        else
            return (0);
    }
    if(dungeon.size() == roomCoordX + 1){
         if(shield + dungeon[roomCoordX][roomCoordY] < 0)
            return (dungeon[roomCoordX][roomCoordY] + shield) + actualFunction(dungeon, roomCoordX, roomCoordY + 1, 0);
        else
            return 0 +  actualFunction(dungeon, roomCoordX, roomCoordY + 1, dungeon[roomCoordX][roomCoordY] + shield);
    }
    if(dungeon[0].size() == roomCoordY + 1){
         if(shield + dungeon[roomCoordX][roomCoordY] < 0)
            return (dungeon[roomCoordX][roomCoordY] + shield) + actualFunction(dungeon, roomCoordX + 1, roomCoordY, 0);
        else
            return 0 +  actualFunction(dungeon, roomCoordX + 1, roomCoordY, dungeon[roomCoordX][roomCoordY] + shield);
    }
        int temp1;
        int temp2;
    if(shield + dungeon[roomCoordX][roomCoordY] < 0){
        temp1 = actualFunction(dungeon, roomCoordX + 1, roomCoordY, 0);
        temp2 = actualFunction(dungeon, roomCoordX, roomCoordY + 1, 0);
        return(shield + dungeon[roomCoordX][roomCoordY]) + ((temp1 > temp2) ? temp1 : temp2);
    }
    else{
        temp1 = actualFunction(dungeon, roomCoordX + 1, roomCoordY, dungeon[roomCoordX][roomCoordY] + shield);
        temp2 = actualFunction(dungeon, roomCoordX, roomCoordY + 1, dungeon[roomCoordX][roomCoordY] + shield);
        return 0 + ((temp1 > temp2) ? temp1 : temp2);
    }
}
};

Answer 1

Dynamic programming solution

This problem can be solved with a dynamic programming solution by starting at the end cell and working upwards and leftwards to the starting cell. The basic premise is:

1. You need to construct a new matrix of values which holds the minimum health required to have before reaching a square. For example, if m[5][3] is 10, it means that you need 10 health to reach the finish, if you were at (4,3) or (5,2) and were about to move to (5,3).

2. Start with the end cell, and set its value to max(1, 1 - dungeon[lastcell]).

3. Then working your way upwards and leftwards, you can set each cell like this:

   downHealth  = max(1, m[downNeighbor ] - d[thiscell]);
   rightHealth = max(1, m[rightNeighbor] - d[thiscell]);
   m[thiscell] = min(downHealth, rightHealth);
   

   Note that some cells do not have both neighbors, so you just set the value to the health computed for the neighbor that exists.