DDSA Solutions

3286. Find a Safe Walk Through a Grid

MediumView on LeetCode
ArrayBreadth-First SearchMatrix
Time: O(m * n * health)
Space: O(m * n * health)

Problem Overview

Treat each move as spending health equal to the destination cell value (0 or 1).

Intuition

Treat each move as spending health equal to the destination cell value (0 or 1). The question is not shortest distance but reachability with positive health left, so the natural state is (row, col, remainingHealth). A plain cell-only visited array is not enough because reaching the same cell with more health is strictly better than reaching it with less.

Algorithm

  1. 1Subtract grid[0][0] from the initial health because entering the start cell also costs health.
  2. 2Run BFS over states (r, c, h), where h is remaining health after standing on that cell.
  3. 3From each state, try the 4 neighbors. The next health is h - grid[nr][nc].
  4. 4Skip moves that leave nextHealth <= 0, because the path must keep health strictly positive.
  5. 5Use seen[r][c][h] so the same cell can still be explored again with a different remaining-health value.
  6. 6If BFS reaches (m-1, n-1) with h > 0, return true; otherwise false.

Example Walkthrough

Input: grid = [[0,1,0],[0,1,0],[0,0,0]], health = 2

  1. 1.Start at (0,0) with health 2 because grid[0][0] = 0.
  2. 2.Going right twice would spend 1 health on the blocked middle column and may trap us.
  3. 3.BFS also explores going down first: (1,0) -> (2,0) -> (2,1) -> (2,2), paying only zeros.
  4. 4.Destination is reached with health still positive, so the answer is true.

Output: true

Common Pitfalls

  • •The start cell cost counts too: initialHealth = health - grid[0][0].
  • •Visited-by-cell alone is incorrect; a later path that reaches the same cell with more remaining health may still succeed.
  • •The condition is strictly positive health, so nextHealth == 0 is not allowed.
3286.cs
C#
// Approach: BFS on state (row, col, remainingHealth). Entering a cell costs grid[r][c],
// so we start with health - grid[0][0]. We can revisit the same cell with different
// remaining health values, so track seen[row,col,health]. If we ever reach the bottom-right
// cell with health > 0, a safe walk exists.
// Time: O(m * n * health) Space: O(m * n * health)
public class Solution
{
    private record T(int i, int j, int h);

    public bool FindSafeWalk(IList<IList<int>> grid, int health)
    {
        int[][] DIRS = new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 }, new int[] { 0, -1 }, new int[] { -1, 0 } };
        int m = grid.Count;
        int n = grid[0].Count;
        int initialHealth = health - grid[0][0];
        var q = new Queue<T>();
        q.Enqueue(new T(0, 0, initialHealth));
        bool[,,] seen = new bool[m, n, health + 1];
        seen[0, 0, initialHealth] = true;

        while (q.Count > 0)
        {
            int sz = q.Count;
            for (int _ = 0; _ < sz; _++)
            {
                var curr = q.Dequeue();
                int i = curr.i, j = curr.j, h = curr.h;
                if (i == m - 1 && j == n - 1 && h > 0)
                    return true;
                for (int k = 0; k < 4; k++)
                {
                    int x = i + DIRS[k][0];
                    int y = j + DIRS[k][1];
                    if (x < 0 || x == m || y < 0 || y == n)
                        continue;
                    int nextHealth = h - grid[x][y];
                    if (nextHealth <= 0 || seen[x, y, nextHealth])
                        continue;
                    q.Enqueue(new T(x, y, nextHealth));
                    seen[x, y, nextHealth] = true;
                }
            }
        }

        return false;
    }
}
Was this solution helpful?

Related Problems