To solve this problem, we need to find the shortest path from the top-left corner to the bottom-right corner of a grid, avoiding obstacles. The solution uses Breadth-First Search (BFS) since it efficiently finds the shortest path in an unweighted grid.

Approach

1. Initial Checks: First, check if the start (top-left) or end (bottom-right) cells are obstacles. If either is an obstacle, return -1 immediately as no path exists.
2. BFS Initialization: Use a queue to manage the BFS process. Each element in the queue is a tuple containing the current row, column, and the number of steps taken to reach that cell.
3. Visited Tracking: Maintain a visited matrix to avoid revisiting cells, which prevents cycles and redundant processing.
4. Direction Exploration: For each cell, explore all four possible directions (up, down, left, right). For each valid direction (within grid bounds, not an obstacle, and not visited), mark the cell as visited and enqueue it with an incremented step count.
5. Termination: If the end cell is reached, return the step count. If the queue is exhausted without reaching the end, return -1 (no path exists).

Solution Code

from collections import deque

def shortest_path(grid):
    if not grid or not grid[0]:
        return -1

    m, n = len(grid), len(grid[0])

    # Check if start or end is blocked
    if grid[0][0] == 1 or grid[m-1][n-1] == 1:
        return -1

    # Directions: up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    visited = [[False for _ in range(n)] for _ in range(m)]
    queue = deque()
    queue.append((0, 0, 0))  # (row, col, steps)
    visited[0][0] = True

    while queue:
        row, col, steps = queue.popleft()

        # Check if we've reached the end
        if row == m-1 and col == n-1:
            return steps

        # Explore all directions
        for dr, dc in directions:
            nr, nc = row + dr, col + dc
            # Check if the new cell is within bounds, not visited, and not an obstacle
            if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 0:
                visited[nr][nc] = True
                queue.append((nr, nc, steps + 1))

    # If queue is empty and end not reached
    return -1

Explanation

• BFS Efficiency: BFS is ideal here because it explores all cells at the current step level before moving to cells at the next step level, ensuring the first time we reach the end cell is via the shortest path.
• Visited Matrix: This matrix ensures we do not process the same cell multiple times, which is crucial for both time and space efficiency.
• Edge Cases: Handles cases like 1x1 grids, blocked start/end cells, and grids with no valid path.

This approach runs in O(mn) time complexity, where m and n are the dimensions of the grid, as each cell is processed once. The space complexity is also O(mn) due to the visited matrix and queue storage.

作者声明:本文包含人工智能生成内容。