Statement

Given a binary matrix, we need to find the length of the shortest path from the top-left cell to the bottom-right cell. We can only move in four directions: up, down, left, and right. Additionally, we can only traverse through cells that contain a '1', while '0' cells are considered obstacles.

Approach

The problem can be approached using a breadth-first search (BFS) algorithm, which is a widely used graph traversal technique. BFS explores nodes in a graph level by level, visiting all nodes at a given level before moving to the next level. This property of BFS makes it well-suited for finding the shortest path.

In the context of a binary matrix, we can consider each cell as a node in the graph, and the valid neighbouring cells as the edges. To find the shortest path from the source cell to the destination cell, we need to explore the graph and keep track of the distance travelled.

1. First, we perform some initial checks to handle edge cases. We ensure that the grid is not empty and that both the source cell (top-left) and destination cell (bottom-right) are accessible (i.e., not blocked by obstacles). If any of these conditions are not met, we return -1 as there is no valid path.

2. We initialize some variables: n represents the size of the grid (assuming it's a square matrix), directions is a list containing the possible movements (up, down, left, right), and queue is a deque (double-ended queue) that will store the cells to be explored.

3. We start the BFS algorithm by adding the source cell (0, 0) to the queue with an initial distance of 1. The distance represents the number of steps taken to reach the current cell.

4. We enter a while loop that continues until the queue is empty. In each iteration, we dequeue a cell from the front of the queue.

5. We check if the dequeued cell is the destination cell (bottom-right corner of the grid). If it is, we return the distance travelled, as we have found the shortest path.

6. If the dequeued cell is not the destination, we proceed to explore its valid neighbours. For each neighbour, we perform the following steps:

   • Calculate the coordinates of the neighbour cell by adding the corresponding values from the directions list to the current cell's coordinates.

   • Check if the new coordinates are within the boundaries of the grid and if the neighbour cell is accessible (contains '0'). If these conditions are satisfied, we enqueue the neighbour cell into the queue with an incremented distance value.

   • To ensure we do not revisit the same cell, we mark it as visited by setting its value to '1'. This prevents loops and guarantees that the shortest path is found.

7. If the loop completes without finding the destination cell, it means there is no valid path from the source to the destination. In this case, we return -1.

Code

from collections import deque

def shortestPathBinaryMatrix(grid):
    # Check if the grid is empty or the source/destination cells are blocked
    if not grid or grid[0][0] == 1 or grid[-1][-1] == 1:
        return -1

    n = len(grid)
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    queue = deque([(0, 0, 1)])

    while queue:
        x, y, distance = queue.popleft()

        if x == n - 1 and y == n - 1:
            return distance

        for dx, dy in directions:
            nx, ny = x + dx, y + dy

            # Check if the new coordinates are within the grid boundaries
            if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0:
                queue.append((nx, ny, distance + 1))
                # Mark the cell as visited by setting it to '1'
                grid[nx][ny] = 1

    return -1

Dry Run

• Example

    grid = [
        [0, 1, 0, 0],
        [0, 0, 0, 1],
        [0, 1, 1, 0],
        [1, 0, 0, 0]
    ]
  
    print(shortestPathBinaryMatrix(grid))  # Output: 6
  

  In this example, we have a 4x4 binary matrix representing obstacles and open paths. The shortest path from the top-left cell (0, 0) to the bottom-right cell (3, 3) has a length of 6.