Knight to Princess (and not reverse direction) solution using binary search


  • 1
    D

    Since most solutions solve it in reverse (which is actually pretty neat), what I cam up with is a front to back (and not back to front) solution that uses binary search to find the smallest HP required to rescue. Running time is O(n^2 log(D)), where D is the maximum value of an integer.

    class Solution {
        bool canSolve(vector<vector<int>> &dungeon, int guess) {
            dungeon[0][0] += guess;
            if (dungeon[0][0] <= 0) return false;
            for (int i = 1; i < dungeon.size(); ++i) {
                dungeon[i][0] += dungeon[i-1][0];
                if (dungeon[i][0] <= 0) {
                    dungeon[i][0] = INT_MIN / 2;
                }
            }
            for (int i = 1; i < dungeon[0].size(); ++i) {
                dungeon[0][i] += dungeon[0][i-1];
                if (dungeon[0][i] <= 0) {
                    dungeon[0][i] = INT_MIN / 2;
                }
            }
            for (int i = 1; i < dungeon.size(); ++i) {
                for (int j = 1; j < dungeon[0].size(); ++j) {
                    dungeon[i][j] += std::max(dungeon[i-1][j], dungeon[i][j-1]);
                    if (dungeon[i][j] <= 0) {
                        dungeon[i][j] = INT_MIN / 2;
                    }
                }
            }
            return dungeon.back().back() != INT_MIN / 2;
        }
    public:
        int calculateMinimumHP(vector<vector<int>>& dungeon) {
            if (dungeon.empty() || dungeon[0].empty()) return 1;
            int lo = 1, hi = INT_MAX;
            int guess = hi;
            int mid = lo + (hi - lo) / 2;
            while (lo != hi) {
                auto dcopy = dungeon;
                bool cs = canSolve(dcopy, mid);
                if (cs) {
                    guess = mid;
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
                mid = lo + (hi - lo) / 2;
            }
            return guess;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.