[leetcode] DungeonGame

package temworkingarea;

/**
* <pre>
* 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.
*
* -2 (K)  -3  3
* -5  -10 1
* 10  30  -5 (P)
*
* 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.
* </pre>
* */
public class DungeonGame {
    public class Solution {

        public int calculateMinimumHP(int[][] dungeon) {

            int row = dungeon.length;
            int column = dungeon[0].length;

            int[][] tem = new int[row][];
            for (int i = 0; i < tem.length; i++) {
                tem[i] = new int[column];
            }

            if (dungeon[row - 1][column - 1] >= 0) {
                tem[row - 1][column - 1] = 1;
            } else {
                tem[row - 1][column - 1] = 1 - dungeon[row - 1][column - 1];
            }

            for (int i = row - 2; i >= 0; i--) {
                tem[i][column - 1] = c(dungeon[i][column - 1],
                        tem[i + 1][column - 1]);
            }

            for (int j = column - 2; j >= 0; j--) {
                tem[row - 1][j] = c(dungeon[row - 1][j], tem[row - 1][j + 1]);
            }

            for (int i = row - 2; i >= 0; i--) {
                for (int j = column - 2; j >= 0; j--) {
                    tem[i][j] = Math.min(c(dungeon[i][j], tem[i + 1][j]),
                            c(dungeon[i][j], tem[i][j + 1]));
                }
            }

            return tem[0][0];
        }

        private int c(int value, int preResult) {
            if (value == 0)
                return preResult;

            if (value > 0) {
                if (value >= preResult)
                    return 1;
                return preResult - value;
            }

            return preResult - value;
        }
    }
}