Dungeon Game

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.

Find the knight's minimum initial health so that he is able to rescue the princess.

Example:

Input:  {{-2,-3,3},{-5,-10,1},{10,30,-5}}
Output: 7

Approach

Java

public class DungeonGame {
    public static void main(String[] args) {
        int[][] dungeon = { { -2, -3, 3 }, { -5, -10, 1 }, { 10, 30, -5 } };
        System.out.println(calculateMinimumHP(dungeon));
    }

    static int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {

                // if we reach at end of the grid
                if (i == m - 1 && j == n - 1) {
                    // if value is positive
                    if (dungeon[i][j] > 0)
                        dungeon[i][j] = 1;

                    // if value is negative
                    else
                        dungeon[i][j] = -1 * dungeon[i][j] + 1;
                }

                // if we are at last row
                else if (i == m - 1) {
                    // if value is positive
                    if (dungeon[i][j] > 0)
                        dungeon[i][j] = Math.max(1, dungeon[i][j + 1] - dungeon[i][j]);

                    // if value is negative
                    else
                        dungeon[i][j] = -1 * dungeon[i][j] + dungeon[i][j + 1];
                }

                // if we are at last column

                else if (j == n - 1) {

                    // if value is positive
                    if (dungeon[i][j] > 0)
                        dungeon[i][j] = Math.max(1, dungeon[i + 1][j] - dungeon[i][j]);

                    // if value is negative
                    else
                        dungeon[i][j] = -1 * dungeon[i][j] + dungeon[i + 1][j];
                }

                // if value at the current cell is positive
                else if (dungeon[i][j] > 0) {

                    int x = Math.max(1, dungeon[i + 1][j] - dungeon[i][j]);
                    int y = Math.max(1, dungeon[i][j + 1] - dungeon[i][j]);

                    // update the current cell value
                    dungeon[i][j] = Math.min(x, y);
                }

                // else the value at current cell is negative
                else
                    dungeon[i][j] = -1 * dungeon[i][j] + Math.min(dungeon[i][j + 1], dungeon[i + 1][j]);
            }
        }
        return dungeon[0][0];
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int calculateMinimumHP(vector<vector<int>>& dungeon) 
{
    int m=dungeon.size();
    int n=dungeon[0].size();
    for(int i=m-1;i>=0;i--)
    {
        for(int j=n-1;j>=0;j--)
        {

            //if we reach at end of the grid
            if(i==m-1&&j==n-1)
            {
                //if value is positive
                if(dungeon[i][j]>0)
                       dungeon[i][j]=1;

                //if value is negative
                else
                    dungeon[i][j]=-1*dungeon[i][j]+1;
            }

          //if we are at last row
          else if(i==m-1)
          {
              //if value is positive
              if(dungeon[i][j]>0)
                     dungeon[i][j]=max(1,dungeon[i][j+1]-dungeon[i][j]);

              //if value is negative
              else
                  dungeon[i][j]=-1*dungeon[i][j]+dungeon[i][j+1];
          }

         //if we are at last column

          else if(j==n-1)
          {

              //if value is positive
               if(dungeon[i][j]>0)
                     dungeon[i][j]=max(1,dungeon[i+1][j]-dungeon[i][j]);

             //if value is negative
              else
                  dungeon[i][j]=-1*dungeon[i][j]+dungeon[i+1][j];
          }

       //if value at the current cell is positive
        else if(dungeon[i][j]>0)
        {
            
            int x=max(1,dungeon[i+1][j]-dungeon[i][j]);
            int y=max(1,dungeon[i][j+1]-dungeon[i][j]);

             //update the current cell value
            dungeon[i][j]=min(x,y);
        }

       //else the value at current cell is negative
        else
                dungeon[i][j]=-1*dungeon[i][j]+min(dungeon[i][j+1],dungeon[i+1][j]);
        }
    }
        return dungeon[0][0];
}
int main()
{
    vector<vector<int>> dungeon={{-2,-3,3},
                                 {-5,-10,1},
                                 {10,30,-5}};
    cout<<calculateMinimumHP(dungeon);
    return 0;
}