2812. Find the Safest Path in a Grid

#php #leetcode #algorithms #programming

Difficulty: Medium

Topics: Staff, Array, Binary Search, Breadth-First Search, Union-Find, Heap (Priority Queue), Matrix, Weekly Contest 357

You are given a 0-indexed 2D matrix grid of size n x n, where (r, c) represents:

A cell containing a thief if grid[r][c] = 1
An empty cell if grid[r][c] = 0

You are initially positioned at cell (0, 0). In one move, you can move to any adjacent cell in the grid, including cells containing thieves.

The safeness factor of a path on the grid is defined as the minimum manhattan distance from any cell in the path to any thief in the grid.

Return the maximum safeness factor of all paths leading to cell (n - 1, n - 1).

An adjacent cell of cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) and (r - 1, c) if it exists.

The Manhattan distance between two cells (a, b) and (x, y) is equal to |a - x| + |b - y|, where |val| denotes the absolute value of val.

Example 1:

Input: grid = [[1,0,0],[0,0,0],[0,0,1]]
Output: 0
Explanation: All paths from (0, 0) to (n - 1, n - 1) go through the thieves in cells (0, 0) and (n - 1, n - 1).

Example 2:

Input: All paths from (0, 0) to (n - 1, n - 1) go through the thieves in cells (0, 0) and (n - 1, n - 1).
Output: 2
Explanation: The path depicted in the picture above has a safeness factor of 2 since:
- The closest cell of the path to the thief at cell (0, 2) is cell (0, 0). The distance between them is | 0 - 0 | + | 0 - 2 | = 2.
- It can be shown that there are no other paths with a higher safeness factor.

Example 3:

Input: grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]
Output: 2
Explanation: The path depicted in the picture above has a safeness factor of 2 since:
- The closest cell of the path to the thief at cell (0, 3) is cell (1, 2). The distance between them is | 0 - 1 | + | 3 - 2 | = 2.
- The closest cell of the path to the thief at cell (3, 0) is cell (3, 2). The distance between them is | 3 - 3 | + | 0 - 2 | = 2.
- It can be shown that there are no other paths with a higher safeness factor.

Constraints:

1 <= grid.length == n <= 400
grid[i].length == n
grid[i][j] is either 0 or 1.
There is at least one thief in the grid.

Hint:

Consider using both BFS and binary search together.
Launch a BFS starting from all the cells containing thieves to calculate d[x][y] which is the smallest Manhattan distance from (x, y) to the nearest grid that contains thieves.
To check if the bottom-right cell of the grid can be reached through a path of safeness factor v, eliminate all cells (x, y) such that grid[x][y] < v. if (0, 0) and (n - 1, n - 1) are still connected, there exists a path between (0, 0) and (n - 1, n - 1) of safeness factor v.
Binary search over the final safeness factor v.

Similar Questions:

1631. Path With Minimum Effort

Solution:

We solve the problem of finding the maximum safeness factor in a grid by combining a multi-source BFS to compute distances to the nearest thief for each cell, followed by a binary search over possible safeness factors and a DFS connectivity check. This approach efficiently handles grids up to 400x400 by transforming the problem into a path existence problem with a threshold.

Approach

Multi-Source BFS to compute the minimum Manhattan distance from each cell to any thief
Binary Search over the safeness factor value (0 to maximum possible distance)
DFS Connectivity Check to verify if a path exists from start to end using only cells with distance >= current threshold
Early Termination during DFS when reaching the destination

Let's implement this solution in PHP: 2812. Find the Safest Path in a Grid

<?php
/**
 * @param Integer[][] $grid
 * @return Integer
 */
function maximumSafenessFactor(array $grid): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maximumSafenessFactor([[1,0,0],[0,0,0],[0,0,1]]) .  "\n"; // Output: 0
echo maximumSafenessFactor([[0,0,1],[0,0,0],[0,0,0]]) .  "\n"; // Output: 2
echo maximumSafenessFactor([[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]) .  "\n"; // Output: 2
?>

Explanation:

Initial Distance Computation

All thief cells are used as initial sources in a BFS queue
BFS propagates outward level by level, assigning each cell its minimum distance to any thief
This effectively computes the "safeness score" for every cell in the grid

Binary Search Strategy

The safeness factor is bounded between 0 and the maximum BFS level
For each candidate value mid, we check if a valid path exists
If a path exists at threshold mid, we try higher values (move left = mid + 1)
Otherwise, we try lower values (move right = mid)

Path Validation with DFS

The DFS explores only cells with distance >= current threshold
Starting from (0,0), it attempts to reach (n-1, n-1)
Marking visited cells prevents infinite loops and improves performance
Returns true immediately when the destination is reached

Complexity Analysis

Time Complexity: O(n² × log(n)) where n is the grid dimension
- BFS: O(n²) to compute all distances
- Binary Search: O(log n) iterations
- Each DFS check: O(n²) in worst case
- Total: O(n² + n² × log n) = O(n² × log n)
Space Complexity: O(n²)
- Distance matrix: O(n²)
- Visited matrix: O(n²)
- Queue for BFS: O(n²) in worst case

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!