2812. Find the Safest Path in a Grid

Array Binary Search Breadth-First Search Union Find Matrix Heap (Priority Queue)

Problem Overview

Path safeness is the minimum Manhattan distance to any thief along the route.

Intuition

Path safeness is the minimum Manhattan distance to any thief along the route. Maximize that bottleneck — a maximin shortest-path problem on an implicit grid graph, analogous to LC 778 (Swim in Rising Water) but with precomputed cell weights.

Algorithm

1Multi-source BFS from every thief (grid cell = 1): dist[r][c] = Manhattan distance to the nearest thief.
2Max-heap Dijkstra from (0,0): state priority = path safeness = min(dist along the path so far).
3Relax a neighbor (nr, nc) with ns = min(current safeness, dist[nr][nc]); push if ns improves best[nr][nc].
4First time the destination is popped, return its safeness (max-heap guarantees maximin optimum).

Example Walkthrough

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

1.Thief at (0,0): dist[0][0]=0, neighbors get 1, then 2, …
2.Start (0,0) has safeness 0; any path must pass near the thief — answer 0.
3.grid = [[0,1,1],[0,0,0],[0,0,0]]: dist[0][0]=1 from thief (0,1); maximin path keeps safeness 1.

Output: 0 / 1 / 2 depending on grid

Common Pitfalls

•Use 4-direction neighbors only — Dc must be {1,-1,0,0}, not {1,0,0,-1} (wrong order creates diagonal moves and corrupts BFS distances).
•Binary search on answer + feasibility BFS also works (~O(n² log n) passes); one maximin Dijkstra is simpler and same asymptotic cost.
•(0,0) and (n-1,n-1) are guaranteed safe (no thieves); dist there is the starting safeness, not infinity.

2812.cs

// Approach: Multi-source BFS labels each cell with Manhattan distance to the nearest thief.
// Maximin path Dijkstra from (0,0): each step keeps min(path safeness, neighbor distance).
// One pass replaces binary search + repeated BFS. Time: O(n^2 log n) Space: O(n^2)
public class Solution
{
    private static readonly int[] Dr = { 0, 0, 1, -1 };
    private static readonly int[] Dc = { 1, -1, 0, 0 };

    public int MaximumSafenessFactor(IList<IList<int>> grid)
    {
        int n = grid.Count;
        int[,] dist = BuildDistToThief(grid, n);
        int[,] best = new int[n, n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                best[i, j] = -1;

        var pq = new PriorityQueue<(int r, int c, int s), int>(
            Comparer<int>.Create((a, b) => b.CompareTo(a)));

        best[0, 0] = dist[0, 0];
        pq.Enqueue((0, 0, best[0, 0]), best[0, 0]);

        while (pq.Count > 0)
        {
            var (r, c, s) = pq.Dequeue();
            if (s != best[r, c])
                continue;
            if (r == n - 1 && c == n - 1)
                return s;

            for (int d = 0; d < 4; d++)
            {
                int nr = r + Dr[d];
                int nc = c + Dc[d];
                if (nr < 0 || nr >= n || nc < 0 || nc >= n)
                    continue;

                int ns = Math.Min(s, dist[nr, nc]);
                if (ns > best[nr, nc])
                {
                    best[nr, nc] = ns;
                    pq.Enqueue((nr, nc, ns), ns);
                }
            }
        }

        return best[n - 1, n - 1];
    }

    private static int[,] BuildDistToThief(IList<IList<int>> grid, int n)
    {
        int[,] dist = new int[n, n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dist[i, j] = -1;

        var q = new Queue<(int r, int c)>();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1)
                {
                    dist[i, j] = 0;
                    q.Enqueue((i, j));
                }
            }
        }

        for (int level = 0; q.Count > 0; level++)
        {
            int sz = q.Count;
            while (sz-- > 0)
            {
                var (r, c) = q.Dequeue();
                for (int d = 0; d < 4; d++)
                {
                    int nr = r + Dr[d];
                    int nc = c + Dc[d];
                    if (nr < 0 || nr >= n || nc < 0 || nc >= n || dist[nr, nc] != -1)
                        continue;
                    dist[nr, nc] = level + 1;
                    q.Enqueue((nr, nc));
                }
            }
        }

        return dist;
    }
}

Was this solution helpful?