Problem Statement

Safest Grid Path An `n x m` grid contains `b` blocked positions. A cell's safety is its Manhattan distance to the nearest blocked position. You may move one cell up, down, left, or right, staying inside the grid. Find the maximum possible safety factor of a path from `(0, 0)` to `(n - 1, m - 1)`. The safety factor of a path is the minimum safety of any cell on that path. Blocked positions are danger sources and may be traversed; their safety is `0`. Input The first line contains `n m b`. Each of the next `b` lines contains two integers `r c`, a blocked position. Output Print the maximum possible safety factor. Constraints - `1 <= n, m <= 500` - `1 <= b <= n * m` - `0 <= r < n`, `0 <= c < m` - Blocked positions are distinct. Example Input: `3 3 1` `1 1` Output: `1` Notes Coordinates are 0-based. If the start or destination is blocked, the answer is `0`.