3286. Find a Safe Walk Through a Grid

Array
BFS
Graph
Matrix
Shortest Path

TIME

O(m * n)

SPACE

O(m * n)

Intuition

Health only drops when you step onto an unsafe (1) cell, and each such cell costs exactly 1. So the health you have left at the end is health minus the number of 1-cells on your path. To maximize surviving health, minimize the number of unsafe cells passed through, a shortest-path problem where entering a cell costs its grid value (0 or 1).

Because every edge weight is 0 or 1, 0-1 BFS with a deque solves it in linear time (no heap needed).

Approach

dist[r][c] = minimum unsafe cells on any path reaching (r, c) (including that cell's own value). Init dist[0][0] = grid[0][0].
0-1 BFS from (0, 0) using a deque:
- Pop the front cell. For each neighbor, the cost to enter it is grid[neighbor].
- If dist[cur] + grid[neighbor] < dist[neighbor], relax it and push front if the added cost is 0, back if it's 1 (keeps the deque monotonically ordered by distance).
Answer: health - dist[m-1][n-1] >= 1.

Complexity

Time: O(m · n), each cell relaxed O(1) times, deque keeps ordering without a heap
Space: O(m · n), distance grid and deque

Edge Cases

Start cell is unsafe → its cost counts immediately
health = 1 → only survivable if a fully-safe path exists (dist = 0)
Both corners must be counted; the answer uses strict >= 1 (must finish with positive health)
Single row/column grid → BFS still handles it

Code

from typing import List
from collections import deque


class Solution:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        """
        3286. Find a Safe Walk Through a Grid
        Time: O(m * n)
        Space: O(m * n)
        """
        m, n = len(grid), len(grid[0])
        INF = float("inf")
        dist = [[INF] * n for _ in range(m)]
        dist[0][0] = grid[0][0]
        dq = deque([(0, 0)])  # front = smaller distance

        while dq:
            r, c = dq.popleft()
            d = dist[r][c]
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n:
                    nd = d + grid[nr][nc]
                    if nd < dist[nr][nc]:
                        dist[nr][nc] = nd
                        if grid[nr][nc] == 0:
                            dq.appendleft((nr, nc))
                        else:
                            dq.append((nr, nc))

        return health - dist[m - 1][n - 1] >= 1

import java.util.ArrayDeque;
import java.util.List;

/**
 * 3286. Find a Safe Walk Through a Grid
 * Time: O(m * n)
 * Space: O(m * n)
 */
class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public boolean findSafeWalk(List<List<Integer>> grid, int health) {
        int m = grid.size(), n = grid.get(0).size();
        int[][] dist = new int[m][n];
        for (int[] row : dist) {
            java.util.Arrays.fill(row, Integer.MAX_VALUE);
        }
        dist[0][0] = grid.get(0).get(0);
        ArrayDeque<int[]> dq = new ArrayDeque<>();
        dq.addFirst(new int[]{0, 0}); // front = smaller distance

        while (!dq.isEmpty()) {
            int[] cell = dq.pollFirst();
            int r = cell[0], c = cell[1], d = dist[r][c];
            for (int[] dir : DIRS) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    int w = grid.get(nr).get(nc);
                    int nd = d + w;
                    if (nd < dist[nr][nc]) {
                        dist[nr][nc] = nd;
                        if (w == 0) {
                            dq.addFirst(new int[]{nr, nc});
                        } else {
                            dq.addLast(new int[]{nr, nc});
                        }
                    }
                }
            }
        }

        return health - dist[m - 1][n - 1] >= 1;
    }
}