Find a Safe Walk Through a Grid

medium graph 0-1 BFS shortest path

Problem

Given an m × n binary grid and an integer health, walk from (0, 0) to (m−1, n−1) moving up/down/left/right. A cell with grid[i][j] = 1 is unsafe and costs 1 health when you stand on it (the start cell counts too). Your health must stay positive throughout. Return true if you can reach the goal with health ≥ 1.

The trick: find the path that loses the least health. Since every cell costs either 0 or 1, this is a shortest-path on a graph with weights in {0, 1} — solved efficiently with 0-1 BFS (a deque-based Dijkstra). The answer is health − minLoss ≥ 1.

Inputgrid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health = 1

Outputtrue

A path along the safe (0) cells loses 0 health, so 1 − 0 = 1 ≥ 1.

grid (rows separated by ; , cells by ,)

health

def findSafeWalk(grid, health):
    m, n = len(grid), len(grid[0])
    INF = float("inf")
    # dist[i][j] = minimum health lost to reach (i, j)
    dist = [[INF] * n for _ in range(m)]
    dist[0][0] = grid[0][0]              # start cell may cost 1
    dq = deque([(0, 0)])                 # 0-1 BFS deque
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while dq:
        i, j = dq.popleft()
        for di, dj in dirs:
            ni, nj = i + di, j + dj
            if 0 <= ni < m and 0 <= nj < n:
                nd = dist[i][j] + grid[ni][nj]
                if nd < dist[ni][nj]:    # found a cheaper way in
                    dist[ni][nj] = nd
                    if grid[ni][nj] == 1:
                        dq.append((ni, nj))      # weight 1 -> back
                    else:
                        dq.appendleft((ni, nj))  # weight 0 -> front
    return health - dist[m - 1][n - 1] >= 1

function findSafeWalk(grid, health) {
  const m = grid.length, n = grid[0].length;
  const INF = Infinity;
  // dist[i][j] = minimum health lost to reach (i, j)
  const dist = Array.from({ length: m }, () => new Array(n).fill(INF));
  dist[0][0] = grid[0][0];                 // start cell may cost 1
  const dq = [[0, 0]];                      // 0-1 BFS deque
  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  while (dq.length) {
    const [i, j] = dq.shift();
    for (const [di, dj] of dirs) {
      const ni = i + di, nj = j + dj;
      if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
        const nd = dist[i][j] + grid[ni][nj];
        if (nd < dist[ni][nj]) {            // found a cheaper way in
          dist[ni][nj] = nd;
          if (grid[ni][nj] === 1) dq.push([ni, nj]);     // weight 1 -> back
          else dq.unshift([ni, nj]);                     // weight 0 -> front
        }
      }
    }
  }
  return health - dist[m - 1][n - 1] >= 1;
}

boolean findSafeWalk(int[][] grid, int health) {
    int m = grid.length, n = grid[0].length;
    int[][] dist = new int[m][n];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
    dist[0][0] = grid[0][0];               // start cell may cost 1
    Deque<int[]> dq = new ArrayDeque<>();   // 0-1 BFS deque
    dq.add(new int[]{0, 0});
    int[][] dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
    while (!dq.isEmpty()) {
        int[] cur = dq.pollFirst();
        int i = cur[0], j = cur[1];
        for (int[] dd : dirs) {
            int ni = i + dd[0], nj = j + dd[1];
            if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
                int nd = dist[i][j] + grid[ni][nj];
                if (nd < dist[ni][nj]) {    // found a cheaper way in
                    dist[ni][nj] = nd;
                    if (grid[ni][nj] == 1) dq.addLast(new int[]{ni, nj});
                    else dq.addFirst(new int[]{ni, nj});
                }
            }
        }
    }
    return health - dist[m - 1][n - 1] >= 1;
}

bool findSafeWalk(vector<vector<int>>& grid, int health) {
    int m = grid.size(), n = grid[0].size();
    const int INF = 1e9;
    vector<vector<int>> dist(m, vector<int>(n, INF));
    dist[0][0] = grid[0][0];               // start cell may cost 1
    deque<pair<int,int>> dq;                // 0-1 BFS deque
    dq.push_back({0, 0});
    int dirs[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
    while (!dq.empty()) {
        auto [i, j] = dq.front(); dq.pop_front();
        for (auto& d : dirs) {
            int ni = i + d[0], nj = j + d[1];
            if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
                int nd = dist[i][j] + grid[ni][nj];
                if (nd < dist[ni][nj]) {    // found a cheaper way in
                    dist[ni][nj] = nd;
                    if (grid[ni][nj] == 1) dq.push_back({ni, nj});
                    else dq.push_front({ni, nj});
                }
            }
        }
    }
    return health - dist[m - 1][n - 1] >= 1;
}

Explanation

We want the path from (0,0) to (m−1, n−1) that loses the least health. Standing on an unsafe cell (value 1) costs one health point; safe cells (value 0) cost nothing. So each step into a neighbor has weight equal to that neighbor's grid value — either 0 or 1.

A graph whose edge weights are all 0 or 1 is the textbook case for 0-1 BFS. Instead of a priority queue, we use a double-ended queue. When we relax an edge of weight 0 we push the neighbor to the front (it is just as cheap as the current node); when the edge has weight 1 we push it to the back. This keeps the deque sorted by distance, giving Dijkstra's correctness in linear time.

dist[i][j] holds the minimum health lost to reach that cell. We seed dist[0][0] = grid[0][0] because the start cell itself may be unsafe. We pop from the front, look at the four neighbors, and if going through the current cell gives a strictly smaller dist, we update it and enqueue at the appropriate end.

When the deque drains, dist[m−1][n−1] is the smallest possible health loss. We can survive exactly when health − dist[m−1][n−1] ≥ 1 — that is, at least one health point remains on arrival.

Example: grid = [[1,1,1],[1,0,1],[1,1,1]] with health = 5. The cheapest route goes through the single safe center cell (1,1), losing 4 health, so 5 − 4 = 1 ≥ 1 → true.

Time: O(m · n) Space: O(m · n)