As Far from Land as Possible

q.append((r, c))

Add land cell coordinates to the BFS queue.

This line is critical because it seeds the BFS with all land cells, ensuring the search expands simultaneously from all sources and finds shortest distances efficiently.

dist += 1

Increment distance at the start of each BFS layer.

Incrementing distance at the start of each BFS layer is the core mechanism that measures how far the BFS has expanded from land, directly yielding the maximum distance to water.

if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:

Check if neighbor is within bounds and is water.

This compound condition is critical to BFS correctness, ensuring only valid, unvisited water cells are enqueued, preventing infinite loops and incorrect distance calculations.

q = deque()

Initialize a queue for BFS traversal.

The queue holds cells to explore in BFS order, enabling layer-by-layer expansion from multiple sources.

if not q or len(q) == n * n:

Check if the queue is empty or full (all land).

If no land or no water exists, the problem has no valid solution, so returning -1 early avoids unnecessary computation.

grid[nr][nc] = 1

Mark the water cell as visited by converting it to land.

Marking visited cells prevents revisiting and ensures BFS progresses correctly without cycles.

return dist

Return the maximum distance found after BFS completes.

After BFS finishes, the distance variable holds the maximum shortest distance from any water cell to land, which is the problem's answer.

if grid[r][c] == 1:

Check if the current cell is land.

Identifying land cells is essential to initialize BFS from all sources simultaneously.

return -1

Return -1 when no valid distance can be computed.

This early return handles edge cases where the grid is all land or all water, as no water cell exists to measure distance from land or vice versa.

dist = -1

Initialize distance counter to -1.

Starting at -1 ensures that after the first BFS layer increment, distance corresponds to the correct number of steps from land to water.

while q:

Continue BFS while there are cells to explore.

The loop processes all reachable water cells layer by layer until no new water cells remain.

r, c = q.popleft()

Dequeue the next cell to process.

FIFO order guarantees BFS explores cells in order of increasing distance from land.

q.append((nr, nc))

Enqueue the newly discovered water cell for BFS expansion.

Adding neighbors to the queue schedules them for processing in the next BFS layer, enabling distance propagation.

directions = [(1,0), (-1,0), (0,1), (0,-1)]

Define the four possible movement directions.

These directions represent the allowed moves (up, down, left, right) for BFS traversal, enabling exploration of adjacent cells.

for _ in range(len(q)):

Iterate over all cells in the current BFS layer.

Processing all cells in the current layer ensures BFS expands uniformly, maintaining correct distance calculations.

for dr, dc in directions:

Iterate over all four possible directions.

Exploring neighbors in all directions ensures BFS covers the entire reachable area from land cells.

nr, nc = r + dr, c + dc

Calculate neighbor cell coordinates.

Computing neighbor positions is necessary to explore adjacent cells during BFS.

for r in range(n):

Iterate over each row index.

This loop scans the entire grid to identify land cells as BFS starting points.

for c in range(n):

Iterate over each column index.

Nested loop ensures every cell in the grid is visited for initialization.

n = len(grid)

Store the grid size n.

Caching the grid dimension simplifies boundary checks and avoids repeated calls to len(grid), improving readability and minor performance.