Shortest Path in Binary Matrix

if (row, col) == (n - 1, n - 1):

Check if the current cell is the target cell.

Identifying the target cell allows immediate termination with the shortest path length, leveraging BFS's layer order.

if grid[0][0] == 1:

Check if the starting cell is blocked.

If the start cell is blocked, no path can begin, so the algorithm must terminate immediately to avoid unnecessary computation.

queue = deque([(0, 0, 1)])

Initialize the BFS queue with the starting cell and initial distance 1.

Starting BFS with the start cell at distance 1 sets the baseline for path length counting and exploration order.

row, col, steps = queue.popleft()

Dequeue the next cell and its current path length.

FIFO dequeue maintains BFS order, guaranteeing layer-by-layer exploration and shortest path discovery.

return steps

Return the number of steps taken to reach the target.

Returning here ensures the shortest path length is reported as soon as the target is reached, which BFS guarantees is minimal.

if valid(next_row, next_col) and (next_row, next_col) not in seen:

Check if the neighbor is valid and unvisited.

This condition ensures BFS only explores cells that are within bounds, unblocked, and not yet visited, preventing cycles and invalid paths.

return -1

Return -1 to indicate no path exists from the start.

Returning early here prevents the BFS from running on an impossible input, improving efficiency and correctness.

return 0 <= row < n and 0 <= col < n and grid[row][col] == 0

Return whether the cell is within bounds and unblocked.

This condition enforces the problem constraints that only cells with value 0 and valid indices can be traversed.

seen = {(0, 0)}

Initialize the visited set with the starting cell.

Marking the start cell as visited prevents revisiting it and infinite loops during BFS.

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

Define all 8 possible movement directions including diagonals.

Including diagonal directions is essential to correctly model the problem's allowed moves and find the shortest path.

seen.add((next_row, next_col))

Mark the neighbor cell as visited.

Marking visited upon enqueueing prevents multiple enqueues of the same cell, ensuring O(n^2) time complexity and correctness.

queue.append((next_row, next_col, steps + 1))

Enqueue the neighbor cell with incremented path length.

Adding neighbors to the queue with steps + 1 schedules them for future exploration at the correct distance layer.

def valid(row, col):

Define a helper function to validate cell coordinates and blockage.

Encapsulating boundary and blockage checks in a function improves code clarity and ensures consistent validation logic.

while queue:

Begin BFS loop, processing cells until queue is empty.

The loop ensures all reachable cells are explored in order of increasing distance, which is fundamental to BFS correctness.

next_row, next_col = row + dy, col + dx

Calculate the coordinates of the neighbor cell.

Correctly computing neighbor coordinates is essential for valid traversal and avoiding errors.

return -1

Return -1 if no path to the target exists after BFS completes.

If BFS exhausts all reachable cells without finding the target, returning -1 correctly signals the absence of any valid path.

for dx, dy in directions:

Iterate over all 8 possible neighbor directions.

Exploring all neighbors is necessary to fully traverse the grid and find the shortest path.

n = len(grid)

Store the grid dimension for boundary checks.

Caching the grid size avoids repeated calls to len(grid) and simplifies boundary validation.