2812. Find the Safest Path in a Grid
Tags: php, leetcode, algorithms, programming
Published: 2024-05-15 15:02:51

2812\. Find the Safest Path in a Grid

Medium

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:**

![example1](https://assets.leetcode.com/uploads/2023/07/02/example1.png)

- **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:**

![example2](https://assets.leetcode.com/uploads/2023/07/02/example2.png)

- **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:**

![example3](https://assets.leetcode.com/uploads/2023/07/02/example3.png)

- **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`.

**Solution:**

```
class Solution {

    /**
     * @param Integer[][] $grid
     * @return Integer
     */
    function maximumSafenessFactor($grid) {
        $n = count($grid);
        $g = array_fill(0, $n, array_fill(0, $n, -1));
        $vis = array_fill(0, $n, array_fill(0, $n, false));
        $q = [];
        for ($i = 0; $i < $n; $i++) {
            for ($j = 0; $j < $n; $j++) {
                if ($grid[$i][$j] === 1) {
                    array_push($q, [$i, $j]);
                }
            }
        }
        $level = 0;
        while (!empty($q)) {
            $t = [];
            foreach ($q as $coord) {
                [$x, $y] = $coord;
                if ($x < 0 || $y < 0 || $x === $n || $y === $n || $g[$x][$y] !== -1) {
                    continue;
                }
                $g[$x][$y] = $level;
                array_push($t, [$x + 1, $y]);
                array_push($t, [$x - 1, $y]);
                array_push($t, [$x, $y + 1]);
                array_push($t, [$x, $y - 1]);
            }
            $q = $t;
            $level++;
        }
        $dfs = function($i, $j, $v) use (&$dfs, $n, &$vis, &$g) {
            if ($i < 0 || $j < 0 || $i === $n || $j === $n || $vis[$i][$j] || $g[$i][$j] <= $v) {
                return false;
            }
            $vis[$i][$j] = true;
            return (
                ($i === $n - 1 && $j === $n - 1) ||
                $dfs($i + 1, $j, $v) ||
                $dfs($i, $j + 1, $v) ||
                $dfs($i - 1, $j, $v) ||
                $dfs($i, $j - 1, $v)
            );
        };

        $left = 0;
        $right = $level;
        while ($left < $right) {
            array_walk($vis, function(&$v) { $v = false; });
            $mid = ($left + $right) >> 1;
            if ($dfs(0, 0, $mid)) {
                $left = $mid + 1;
            } else {
                $right = $mid;
            }
        }
        return $right;
    }
}
```

**Contact Links**

- **[LinkedIn](https://www.linkedin.com/in/arifulhaque/)**
- **[GitHub](https://github.com/mah-shamim)**