Rat's Safest Path — Maximize Distance from the Cat

Problem Statement

You are given an N × N grid where each cell is either land (1) or water (0). A rat starts at a source cell (sx, sy) and must reach a target cell (tx, ty), moving one step at a time in the four cardinal directions (up, down, left, right). It may only move onto open (land) cells.

A cat sits stationary at cell (cx, cy).

The safety of a path is defined as the minimum Manhattan distance from the cat among all cells visited on that path. Find a valid path from source to target that maximizes this safety value.

Return the maximum possible safety value. If no valid path exists, return -1.

Constraints

• 1 <= N <= 500
• Grid cells are 0 (water) or 1 (land)
• Source, target, and cat positions are valid coordinates
• Movement is 4-directional, only onto land cells

Example

Grid (1 = land, 0 = water):
1 1 1
1 0 1
1 1 1

source = (0,0), target = (2,2), cat = (0,2)

The rat wants a route from (0,0) to (2,2) that stays as far from the cat at (0,2) as possible. The answer is the largest value d such that a path exists using only cells whose Manhattan distance to the cat is ≥ d.

What the Interviewer Expects

This is a "maximize the minimum" path problem — a classic signal for binary search on the answer combined with a reachability check.

Approach 1 — Binary Search + BFS/DFS (clean):

1. The safety value is bounded between 0 and the max possible Manhattan distance on the grid.
2. Binary search on a candidate safety d.
3. Feasibility check: can the rat go source → target using ONLY cells where manhattanDistanceToCat(cell) >= d (and the cell is land)? Run BFS/DFS over that restricted grid.
4. If reachable → try a larger d. Else → smaller. The largest feasible d is the answer.
5. Complexity: O(N² · log(maxDist)).

Approach 2 — Max-heap (Dijkstra-style, often cleaner):

• Precompute each cell's Manhattan distance to the cat.
• Use a max-heap keyed by "the minimum safety along the best path to reach this cell."
• Pop the cell with the highest achievable safety, relax neighbors (a neighbor's achievable safety = min(current cell's safety, neighbor's distance to cat)).
• When you pop the target, that's the answer. This is the "maximize bottleneck path" pattern (like LeetCode's "Path With Maximum Minimum Value").

Both give the same result; the heap version avoids the binary-search loop.

Follow-ups

1. Multiple cats: How do you handle it? (Use multi-source BFS from all cats first to compute each cell's distance to the NEAREST cat, then the rest of the algorithm is identical — safety is still the min-distance-to-any-cat along the path.)
2. What if the cat could also move each turn? How does that change the problem?
3. What if you wanted the actual path, not just the safety value?
4. Why does binary search work here — what's the monotonic property? (If safety d is achievable, so is any d' < d.)
5. Compare the binary-search approach vs the max-heap approach — when is each preferable?