Mouse-to-Cheese Grid Path That Maximizes the Minimum Distance to a Cat
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an `N x N` grid that contains a mouse's starting cell `S`, a piece of cheese at `T`, a cat at `C`, water cells and land cells. The mouse moves one step at a time up, down, left or right, and it can never enter a water cell. The cat does not move.
The safety of a path is the smallest Manhattan distance from any cell on the path, including `S` and `T`, to the cat's cell. Return the largest safety over all paths from `S` to `T`, or `-1` if the mouse cannot reach `T` at all.
Each row of the grid is a string over the characters `'S'`, `'T'`, `'C'`, `'.'` (land) and `'W'` (water). Cells are written as `(row, column)`, 0-indexed.
### Function Signature
```python
def max_safety(grid: list[str]) -> int:
```
### Rules
- The Manhattan distance between `(r1, c1)` and `(r2, c2)` is `|r1 - r2| + |c1 - c2|`. It is measured on grid coordinates and ignores any water between the two cells.
- A path is a sequence of cells that starts at `S`, ends at `T`, contains no water cell, and in which consecutive cells share a side. Cells may be revisited.
- `S`, `T` and `C` are land. The mouse may step onto the cat's cell, whose distance to the cat is `0`.
- Return only the largest safety, not the path.
### Constraints
- `2 <= N <= 500`, where `N = len(grid)` and `len(grid[i]) == N` for every row `i`
- The grid contains exactly one `'S'`, exactly one `'T'` and exactly one `'C'`. Every other character is `'.'` or `'W'`.
- Every distance is at most `2 * (N - 1) = 998`.
### Examples
**Example 1**
```text
Input: grid = [
"S...T",
".....",
"..C..",
".....",
"....."
]
Output: 2
```
`S` is in column `0` and `T` is in column `4`, so every path visits column `2`, whose cells are at distances `2, 1, 0, 1, 2` from the cat. Walking along the top row keeps every cell at distance at least `2`.
**Example 2**
```text
Input: grid = [
"S.W.T",
".....",
"..C..",
".....",
"..W.."
]
Output: 1
```
The water at `(0, 2)` and `(4, 2)` leaves `(1, 2)`, `(2, 2)` and `(3, 2)` as the only ways across column `2`, and the best of them is at distance `1`. The path `S`, `(1, 0)`, `(1, 1)`, `(1, 2)`, `(1, 3)`, `(1, 4)`, `T` achieves it.
**Example 3**
```text
Input: grid = [
"SW..",
"W...",
"..C.",
"...T"
]
Output: -1
```
Both neighbors of `S` are water, so the cheese cannot be reached.
Overview: Find a path for a mouse from its start cell to the cheese on a grid with water cells, such that the closest the path ever comes to a stationary cat, measured by Manhattan distance, is as large as possible. It tests bottleneck path search on a grid, distance computations and handling an unreachable target.
Read the full Google Software Engineer interview experience this question came from