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
A mouse starts at cell `S` of an `N x N` grid and wants to reach the cheese at cell `T`. A cat sits at cell `C` and never moves. Every other cell is land (`'.'`) or water (`'W'`). The mouse moves one step at a time up, down, left or right, and it can never enter a water cell.
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. Implement `max_safety(grid)`, which returns the largest safety over all paths from `S` to `T`, or `-1` if the mouse cannot reach `T` at all.
`grid` is a list of `N` strings. Each row is a string over the characters `'S'`, `'T'`, `'C'`, `'.'` (land) and `'W'` (water). Cells are written as `(row, column)`, 0-indexed.
**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.
Because every distance is at most `2 * (N - 1) = 998`, the result is either `-1` or an integer from `0` to `998`. It never exceeds `2^31 - 1`, so a 32-bit `int` is enough in every language.
**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 at `(2, 2)`. Walking along the top row keeps every cell at distance at least `2`.
**Example 2**
```text
Input: grid = [
'SW..',
'W...',
'..C.',
'...T'
]
Output: -1
```
Both neighbors of `S` are water, so the cheese cannot be reached.
**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`.
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
Input: (['S...T', '.....', '..C..', '.....', '.....'],)
Expected Output: 2
Explanation: Source example 1: every route crosses column 2, and the top row keeps every cell at distance at least 2.
Input: (['S.W.T', '.....', '..C..', '.....', '..W..'],)
Expected Output: 1
Explanation: Source example 2: water at (0, 2) and (4, 2) forces the crossing through (1, 2), (2, 2) or (3, 2), and the best of them is at distance 1.
Hints
- A cell's distance to the cat is pure coordinate arithmetic: water between the cell and the cat does not make it any farther, so every cell's distance can be computed without a search.
- S and T lie on every path, so the answer can never exceed the smaller of their two distances. If T cannot be reached even when every land cell (the cat's included) is allowed, the answer is -1.
- If the mouse can keep every cell at distance at least d from the cat, it can also keep every cell at distance at least d - 1. Use that monotonic structure.
Community answers
Answer by Coderka14
#include
using namespace std;
class Solution
{
public:
int n;
int cr, cc;
pair S, T;
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};
bool canReach(vector& grid, int safety)
{
int startDist = abs(S.first - cr) + abs(S.second - cc);
if (startDist < safety)
return false;
queue> q;
vector> vis(n, vector(n, false));
q.push(S);
vis[S.first][S.second] = true;
while (!q.empty())
{
auto [r, c] = q.front();
q.pop();
if (r == T.first && c == T.second)
return true;
for (int k = 0; k < 4; k++)
{
int nr = r + dr[k];
int nc = c + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= n)
continue;
if (vis[nr][nc])
continue;
if (grid[nr][nc] == 'W')
continue;
int distFromCat = abs(nr - cr) + abs(nc - cc);
if (distFromCat < safety)
continue;
vis[nr][nc] = true;
q.push({nr, nc});
}
}
return false;
}
int max_safety(vector& grid)
{
n = grid.size();
for (int r = 0; r < n; r++)
{
for (int c = 0; c < n; c++)
{
if (grid[r][c] == 'S')
S = {r, c};
else if (grid[r][c] == 'T')
T = {r, c};
else if (grid[r][c] == 'C')
{
cr = r;
cc = c;
}
}
}
int lo = 0;
int hi = 2 * (n - 1);
int ans = -1;
while (lo <= hi)
{
int mid = lo + (hi - lo) / 2;
if (canReach(grid, mid))
{
ans = mid;
lo = mid + 1;
}
else
{
hi = mid - 1;
}
}
return ans;
}
};