> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Find the Safest Path in a Grid Python Solution

> Tested Python solution for LeetCode 2812 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 2812, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Binary Search](/catalog/topics/binary-search), [Breadth-First Search](/catalog/topics/breadth-first-search), [Union-Find](/catalog/topics/union-find), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue), [Matrix](/catalog/topics/matrix). [View on LeetCode](https://leetcode.com/problems/find-the-safest-path-in-a-grid/description/).

Generate this problem as a practice environment: tested reference solution, 16 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2812   # by problem number
lcpy gen -s find_the_safest_path_in_a_grid   # by problem name
```

## Problem

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.

### Examples

![Example 1](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](https://assets.leetcode.com/uploads/2023/07/02/example2.png)

```
Input: grid = [[0,0,1],[0,0,0],[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, 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](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

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_the_safest_path_in_a_grid/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_the_safest_path_in_a_grid/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import deque
from heapq import heappop, heappush


class Solution:
    # Time: O(n^2 log(n^2)) for the multi-source BFS plus the maximin search
    # Space: O(n^2)
    def maximum_safeness_factor(self, grid: list[list[int]]) -> int:
        n = len(grid)
        dist = self._thief_distances(grid, n)
        best = [[-1] * n for _ in range(n)]
        best[0][0] = dist[0][0]
        heap: list[tuple[int, int, int]] = [(-dist[0][0], 0, 0)]
        while heap:
            neg, r, c = heappop(heap)
            safe = -neg
            if safe < best[r][c]:
                continue
            if r == n - 1 and c == n - 1:
                return safe
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n:
                    nxt = min(safe, dist[nr][nc])
                    if nxt > best[nr][nc]:
                        best[nr][nc] = nxt
                        heappush(heap, (-nxt, nr, nc))
        return best[n - 1][n - 1]

    def _thief_distances(self, grid: list[list[int]], n: int) -> list[list[int]]:
        dist = [[-1] * n for _ in range(n)]
        queue = deque((r, c) for r in range(n) for c in range(n) if grid[r][c] == 1)
        for r, c in queue:
            dist[r][c] = 0
        while queue:
            r, c = queue.popleft()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and dist[nr][nc] < 0:
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))
        return dist
```

## Complexity

| Time | Space |
| - | - |
| O(n^2 log(n^2)) for the multi-source BFS plus the maximin search | O(n^2) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.