Reach a Grid Corner with Positive Health

# Reach a Grid Corner with Positive Health ### Problem You are given an `m x n` binary matrix `grid` and an integer `health`. Start at `(0, 0)` and try to reach `(m - 1, n - 1)`. You may move one cell up, down, left, or right within the grid. A cell whose value is `1` is unsafe and costs one health point when you occupy it, including the starting cell and the destination. A cell whose value is `0` costs no health. Your health must remain strictly positive throughout the walk. Return `true` if some walk reaches the destination with at least one health point left; otherwise return `false`. ### C++ Interface ```cpp class Solution { public: bool findSafeWalk(vector<vector<int>>& grid, int health); }; ``` ### Examples #### Example 1 **Input:** `grid = [[1,0,1],[1,0,0]], health = 2` **Output:** `true` **Explanation:** Follow `(0,0) -> (0,1) -> (1,1) -> (1,2)`. The starting cell costs one health point; the other cells on this walk are safe. You reach the destination with one point left. #### Example 2 **Input:** `grid = [[0,1],[1,1]], health = 2` **Output:** `false` **Explanation:** Reaching the destination requires occupying at least one unsafe intermediate cell and the unsafe destination. These two health losses leave zero health, which is not allowed. ### Constraints - `m == grid.size()` and `n == grid[i].size()` - `1 <= m, n <= 50` - `2 <= m * n` - `1 <= health <= m + n` - Each `grid[i][j]` is either `0` or `1`. - All indices are zero-based. ### Clarifying Questions - Does an unsafe starting cell consume health? Yes, before the first move. - Is arriving with zero health sufficient? No, the final health must be at least one. - Are moves restricted to right and down? No, all four orthogonal directions are allowed. ### What a Strong Answer Covers - Health accounting at both endpoints and the strict positive-health requirement. - Why the existence decision remains correct when different routes meet at the same cell or revisit cells. - Coverage of all four movement directions, with a correctness argument and bounds for a `50 x 50` grid. - Cases with zero-cost routes and routes whose fewest moves differ from their least health loss. ### Follow-up Questions - Why can a longer walk lose less health than a shorter one? - How would the final comparison change if health were allowed to be zero throughout the walk? ```hint Compare arrivals at the same cell An arrival with more remaining health can follow every continuation available to an arrival with less health. What single best value could you retain for each cell? ``` ```hint Separate health loss from move count Moving into a cell costs either zero or one health point. Find the smallest total loss, remembering the cost of the starting cell. ```