Find the Maximum Safeness of a Grid Path
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Find the Maximum Safeness of a Grid Path
You are given a 0-indexed `n x n` matrix `grid`. A cell contains a thief when its value is `1` and is empty when its value is `0`.
Start at `(0,0)` and reach `(n - 1,n - 1)`. Each move goes to an existing cell directly above, below, left, or right. You may enter cells containing thieves.
The safeness factor of a path is the minimum Manhattan distance between any cell on the path and any thief anywhere in the grid. The Manhattan distance between `(a,b)` and `(x,y)` is `|a - x| + |b - y|`.
Return the largest safeness factor among all paths from the start to the destination.
### Examples
**Example 1**
```text
Input: grid = [[0,1],[0,0]]
Output: 1
```
The path `(0,0) -> (1,0) -> (1,1)` stays at distances `1`, `2`, and `1` from the thief at `(0,1)`. It achieves safeness `1`. The start is only one unit from that thief, so no path can do better.
**Example 2**
```text
Input: grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
Output: 3
```
Go down the left edge and then right along the bottom edge. Distances to the sole thief at `(0,3)` are `3,4,5,6,5,4,3`, giving safeness `3`. Both endpoints have distance `3`, which is also an upper bound on every path's safeness.
### Constraints
- `1 <= grid.length == n <= 400`.
- `grid[i].length == n`.
- Every `grid[i][j]` is either `0` or `1`.
- There is at least one thief in the grid.
### Clarifying Questions
- Are thief cells blocked? No; entering one is allowed, but any path that does has safeness zero.
- Do start and destination cells count toward the minimum? Yes; both belong to the path.
- Are diagonal moves allowed? No; only the four listed directions are allowed.
- Does the nearest thief have to lie on the path? No; every thief in the grid affects the distance.
- Is the objective to minimize path length? No; maximize the minimum distance to a thief along the path.
### C++ Interface
```cpp
class Solution {
public:
int maximumSafenessFactor(vector<vector<int>>& grid) {
}
};
```
### Reasoning Checkpoints
- Include off-path thieves and both endpoint cells in the safeness definition.
- Distinguish the binary thief indicator from an actual distance to the nearest thief.
- Justify optimality over all legal four-direction paths, including paths with safeness zero.
```hint A candidate safeness
For a fixed proposed safeness value, which cells can belong to a path achieving at least that value?
```
Overview: Find a four-direction grid path that maximizes its minimum Manhattan distance to any thief, with thief cells still permitted on paths.