2812. Find the Safest Path in a Grid

import java.util.*;

class Solution {
    private int n;
    private int[][] dist;
    private final int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};

    public int maximumSafenessFactor(List<List<Integer>> grid) {
        n = grid.size();
        dist = new int[n][n];

        for (int[] row : dist) Arrays.fill(row, -1);

        Queue<int[]> q = new LinkedList<>();

        // Multi-source BFS from all thieves
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 1) {
                    dist[i][j] = 0;
                    q.offer(new int[]{i, j});
                }
            }
        }

        while (!q.isEmpty()) {
            int[] cur = q.poll();

            for (int[] d : dirs) {
                int x = cur[0] + d[0];
                int y = cur[1] + d[1];

                if (x >= 0 && x < n && y >= 0 && y < n && dist[x][y] == -1) {
                    dist[x][y] = dist[cur[0]][cur[1]] + 1;
                    q.offer(new int[]{x, y});
                }
            }
        }

        int low = 0, high = 2 * n;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (canReach(mid)) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return high;
    }

    private boolean canReach(int limit) {
        if (dist[0][0] < limit) return false;

        boolean[][] vis = new boolean[n][n];
        Queue<int[]> q = new LinkedList<>();

        q.offer(new int[]{0, 0});
        vis[0][0] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();

            if (cur[0] == n - 1 && cur[1] == n - 1) {
                return true;
            }

            for (int[] d : dirs) {
                int x = cur[0] + d[0];
                int y = cur[1] + d[1];

                if (x >= 0 && x < n && y >= 0 && y < n &&
                    !vis[x][y] && dist[x][y] >= limit) {

                    vis[x][y] = true;
                    q.offer(new int[]{x, y});
                }
            }
        }

        return false;
    }
}

from collections import deque

class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]

        dist = [[-1] * n for _ in range(n)]
        q = deque()

        # Multi-source BFS from all thieves
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    dist[i][j] = 0
                    q.append((i, j))

        while q:
            x, y = q.popleft()

            for dx, dy in dirs:
                nx, ny = x + dx, y + dy

                if 0 <= nx < n and 0 <= ny < n and dist[nx][ny] == -1:
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))

        def canReach(limit):
            if dist[0][0] < limit:
                return False

            vis = [[False] * n for _ in range(n)]
            q = deque([(0, 0)])
            vis[0][0] = True

            while q:
                x, y = q.popleft()

                if x == n - 1 and y == n - 1:
                    return True

                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy

                    if (0 <= nx < n and 0 <= ny < n and
                        not vis[nx][ny] and dist[nx][ny] >= limit):

                        vis[nx][ny] = True
                        q.append((nx, ny))

            return False

        low, high = 0, 2 * n

        while low <= high:
            mid = (low + high) // 2

            if canReach(mid):
                low = mid + 1
            else:
                high = mid - 1

        return high

class Solution {
    int n;
    vector<vector<int>> dist;
    vector<vector<int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};

public:
    int maximumSafenessFactor(vector<vector<int>>& grid) {
        n = grid.size();
        dist.assign(n, vector<int>(n, -1));

        queue<pair<int,int>> q;

        // Multi-source BFS from all thieves
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                    q.push({i, j});
                }
            }
        }

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();

            for (auto &d : dirs) {
                int nx = x + d[0];
                int ny = y + d[1];

                if (nx >= 0 && nx < n && ny >= 0 && ny < n && dist[nx][ny] == -1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }

        int low = 0, high = 2 * n;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (canReach(mid))
                low = mid + 1;
            else
                high = mid - 1;
        }

        return high;
    }

    bool canReach(int limit) {
        if (dist[0][0] < limit)
            return false;

        vector<vector<bool>> vis(n, vector<bool>(n, false));
        queue<pair<int,int>> q;

        q.push({0, 0});
        vis[0][0] = true;

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();

            if (x == n - 1 && y == n - 1)
                return true;

            for (auto &d : dirs) {
                int nx = x + d[0];
                int ny = y + d[1];

                if (nx >= 0 && nx < n && ny >= 0 && ny < n &&
                    !vis[nx][ny] && dist[nx][ny] >= limit) {

                    vis[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }

        return false;
    }
};

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maximumSafenessFactor = function(grid) {
    const n = grid.length;
    const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

    const dist = Array.from({ length: n }, () => Array(n).fill(-1));
    const q = [];
    let head = 0;

    // Multi-source BFS from all thieves
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                dist[i][j] = 0;
                q.push([i, j]);
            }
        }
    }

    while (head < q.length) {
        const [x, y] = q[head++];

        for (const [dx, dy] of dirs) {
            const nx = x + dx;
            const ny = y + dy;

            if (nx >= 0 && nx < n && ny >= 0 && ny < n && dist[nx][ny] === -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push([nx, ny]);
            }
        }
    }

    function canReach(limit) {
        if (dist[0][0] < limit)
            return false;

        const vis = Array.from({ length: n }, () => Array(n).fill(false));
        const queue = [[0, 0]];
        let idx = 0;

        vis[0][0] = true;

        while (idx < queue.length) {
            const [x, y] = queue[idx++];

            if (x === n - 1 && y === n - 1)
                return true;

            for (const [dx, dy] of dirs) {
                const nx = x + dx;
                const ny = y + dy;

                if (nx >= 0 && nx < n && ny >= 0 && ny < n &&
                    !vis[nx][ny] && dist[nx][ny] >= limit) {

                    vis[nx][ny] = true;
                    queue.push([nx, ny]);
                }
            }
        }

        return false;
    }

    let low = 0;
    let high = 2 * n;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);

        if (canReach(mid))
            low = mid + 1;
        else
            high = mid - 1;
    }

    return high;
};