Find the Safest Path in a Grid

medium graph bfs binary search grid

Problem

You are given an n x n 0-indexed grid where each cell is either 1 (a thief) or 0 (empty). The safeness factor of a path is the minimum Manhattan distance from any cell on the path to any thief. Starting at (0, 0) and ending at (n-1, n-1), moving in the four cardinal directions, return the maximum safeness factor over all such paths.

Two phases. First a multi-source BFS from every thief at once labels each cell with its distance to the nearest thief. Then we want the path whose weakest (smallest-distance) cell is as large as possible — a classic max-min search solved by binary search on the threshold: for a candidate value, can we walk start→end touching only cells whose distance is at least that value?

Input

Output2

A path bending through the middle keeps distance ≥ 2 from both thieves, and no path does better.

grid (square, rows by ';', cells 0/1 by space; 1 = thief)

from collections import deque

def maximum_safeness_factor(grid):
    n = len(grid)
    DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
    dist = [[-1] * n for _ in range(n)]
    q = deque()
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 1:
                dist[r][c] = 0
                q.append((r, c))
    while q:
        r, c = q.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))

    def reachable(th):
        if dist[0][0] < th:
            return False
        seen = [[False] * n for _ in range(n)]
        st = [(0, 0)]
        seen[0][0] = True
        while st:
            r, c = st.pop()
            if (r, c) == (n - 1, n - 1):
                return True
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and dist[nr][nc] >= th:
                    seen[nr][nc] = True
                    st.append((nr, nc))
        return False

    lo, hi, ans = 0, min(dist[0][0], dist[n - 1][n - 1]), 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if reachable(mid):
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

function maximumSafenessFactor(grid) {
  const n = grid.length;
  const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  const dist = Array.from({ length: n }, () => new Array(n).fill(-1));
  let q = [];
  for (let r = 0; r < n; r++)
    for (let c = 0; c < n; c++)
      if (grid[r][c] === 1) { dist[r][c] = 0; q.push([r, c]); }
  for (let h = 0; h < q.length; h++) {
    const [r, c] = q[h];
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < n && nc < n && dist[nr][nc] === -1) {
        dist[nr][nc] = dist[r][c] + 1;
        q.push([nr, nc]);
      }
    }
  }
  function reachable(th) {
    if (dist[0][0] < th) return false;
    const seen = Array.from({ length: n }, () => new Array(n).fill(false));
    const st = [[0, 0]]; seen[0][0] = true;
    while (st.length) {
      const [r, c] = st.pop();
      if (r === n - 1 && c === n - 1) return true;
      for (const [dr, dc] of DIRS) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nc >= 0 && nr < n && nc < n && !seen[nr][nc] && dist[nr][nc] >= th) {
          seen[nr][nc] = true; st.push([nr, nc]);
        }
      }
    }
    return false;
  }
  let lo = 0, hi = Math.min(dist[0][0], dist[n - 1][n - 1]), ans = 0;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (reachable(mid)) { ans = mid; lo = mid + 1; }
    else hi = mid - 1;
  }
  return ans;
}

class Solution {
    int n;
    int[][] dist;
    int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
    public int maximumSafenessFactor(List<List<Integer>> g) {
        n = g.size();
        dist = new int[n][n];
        for (int[] row : dist) Arrays.fill(row, -1);
        Queue<int[]> q = new LinkedList<>();
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++)
                if (g.get(r).get(c) == 1) { dist[r][c] = 0; q.offer(new int[]{r, c}); }
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] d : DIRS) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr >= 0 && nc >= 0 && nr < n && nc < n && dist[nr][nc] == -1) {
                    dist[nr][nc] = dist[cur[0]][cur[1]] + 1;
                    q.offer(new int[]{nr, nc});
                }
            }
        }
        int lo = 0, hi = Math.min(dist[0][0], dist[n-1][n-1]), ans = 0;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (reachable(mid)) { ans = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        return ans;
    }
    boolean reachable(int th) {
        if (dist[0][0] < th) return false;
        boolean[][] seen = new boolean[n][n];
        Deque<int[]> st = new ArrayDeque<>();
        st.push(new int[]{0, 0}); seen[0][0] = true;
        while (!st.isEmpty()) {
            int[] cur = st.pop();
            if (cur[0] == n - 1 && cur[1] == n - 1) return true;
            for (int[] d : DIRS) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr >= 0 && nc >= 0 && nr < n && nc < n && !seen[nr][nc] && dist[nr][nc] >= th) {
                    seen[nr][nc] = true; st.push(new int[]{nr, nc});
                }
            }
        }
        return false;
    }
}

class Solution {
    int n;
    vector<vector<int>> dist;
    int DIRS[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    bool reachable(int th) {
        if (dist[0][0] < th) return false;
        vector<vector<bool>> seen(n, vector<bool>(n, false));
        vector<pair<int,int>> st = {{0, 0}}; seen[0][0] = true;
        while (!st.empty()) {
            auto [r, c] = st.back(); st.pop_back();
            if (r == n - 1 && c == n - 1) return true;
            for (auto& d : DIRS) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nc >= 0 && nr < n && nc < n && !seen[nr][nc] && dist[nr][nc] >= th) {
                    seen[nr][nc] = true; st.push_back({nr, nc});
                }
            }
        }
        return false;
    }
public:
    int maximumSafenessFactor(vector<vector<int>>& grid) {
        n = grid.size();
        dist.assign(n, vector<int>(n, -1));
        queue<pair<int,int>> q;
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++)
                if (grid[r][c] == 1) { dist[r][c] = 0; q.push({r, c}); }
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (auto& d : DIRS) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nc >= 0 && nr < n && nc < n && dist[nr][nc] == -1) {
                    dist[nr][nc] = dist[r][c] + 1;
                    q.push({nr, nc});
                }
            }
        }
        int lo = 0, hi = min(dist[0][0], dist[n-1][n-1]), ans = 0;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (reachable(mid)) { ans = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        return ans;
    }
};

Explanation

Safeness of a path is decided by its weakest cell — the one closest to a thief. We first need to know, for every cell, how far it is from the nearest thief.

Multi-source BFS. We seed the queue with all thieves at distance 0 and expand outward simultaneously. Because every source starts together and BFS grows in rings, the first time a cell is reached its label is exactly its distance to the closest thief. This fills the whole dist grid in one sweep.

Binary search on the answer. Higher safeness is always harder to achieve, so the set of feasible safeness values is monotone: if a path with safeness k exists, one with safeness k-1 trivially does too. That lets us binary-search the largest feasible k. For a candidate th, a simple DFS/BFS checks whether we can get from (0,0) to (n-1,n-1) stepping only on cells with dist ≥ th.

The high end of the search is min(dist[0][0], dist[n-1][n-1]) because the path must include both corners, so the answer can never exceed the safer of the two endpoints.

Worked example: the BFS labels reach value 2 in the middle of the board. Threshold 2 is reachable, threshold 3 is not, so the answer is 2.

Time: O(n² log n) Space: O(n²)