# Optimal Commute: Nearest Transit Distance in a City Grid A downtown is modeled as an `m x n` grid `city`. Each cell holds one of three values: - `0` — an open street square you can walk through. - `1` — a building, which is impassable. - `2` — a transit station. From an open street square you may move one step **up, down, left, or right** into an adjacent open street square (`0`) or an adjacent transit station (`2`). You can never move into or through a building (`1`). For each open street square, its **commute cost** is the minimum number of moves needed to reach the *nearest* transit station. A planner wants this cost for every square so they can see how well-served each part of downtown is. ## Task Return a 2D array `dist` with the same dimensions as `city`, where: - `dist[i][j] = 0` if `city[i][j] == 2` (the square is itself a station). - `dist[i][j] = -1` if `city[i][j] == 1` (the square is a building). - `dist[i][j] = k` if `city[i][j] == 0` and the nearest reachable station is exactly `k` moves away (`k >= 1`). - `dist[i][j] = -1` if `city[i][j] == 0` but **no** station is reachable from it. (Both buildings and unreachable open squares are reported as `-1`.) ## Input / Output Format - Input: `city`, a list of `m` rows, each a list of `n` integers drawn from `{0, 1, 2}`. - Output: `dist`, a list of `m` rows, each a list of `n` integers, following the rules above. Function signature: ``` nearest_transit(city: List[List[int]]) -> List[List[int]] ``` ## Constraints & Assumptions - `1 <= m, n <= 300` (up to 90,000 cells). - Every cell of `city` is `0`, `1`, or `2`. - There may be zero, one, or many station cells. - Distances count moves between cell centers; adjacency is 4-directional only (no diagonals). - The expected solution runs in `O(m * n)` time and `O(m * n)` extra space, independent of how many stations there are. ## Example 1 Input: ``` city = [[0, 1, 2], [0, 0, 0], [2, 1, 0]] ``` Output: ``` [[ 2, -1, 0], [ 1, 2, 1], [ 0, -1, 2]] ``` Explanation: Stations sit at `(0,2)` and `(2,0)`. For example, the top-left square `(0,0)` reaches the station at `(2,0)` in 2 moves (down, down), so its commute cost is `2`. The square `(1,1)` reaches either station in 2 moves. The two building cells `(0,1)` and `(2,1)` are reported as `-1`. ## Example 2 Input: ``` city = [[2, 1, 0]] ``` Output: ``` [[0, -1, -1]] ``` Explanation: The only station is at `(0,0)`. The open square at `(0,2)` is walled off from it by the building at `(0,1)`, so it is unreachable and reported as `-1`. The building cell is also `-1`. ## Example 3 Input: ``` city = [[0, 0, 0], [0, 2, 0], [0, 0, 0]] ``` Output: ``` [[2, 1, 2], [1, 0, 1], [2, 1, 2]] ``` Explanation: A single central station fills the surrounding squares with their move-distances to it.