Practice/Amazon/Leetcode 1091. Shortest Path in Binary Matrix

Leetcode 1091. Shortest Path in Binary Matrix

CodingMust

Problem

You are given an n × n square grid where each cell contains either 0 or 1. A cell with value 0 represents an open space that you can walk through, while a cell with value 1 represents a blocked obstacle that cannot be traversed.

Your task is to find the length of the shortest path from the top-left corner cell at position (0, 0) to the bottom-right corner cell at position (n-1, n-1). You can move in all 8 directions: up, down, left, right, and the four diagonal directions.

The path length is defined as the number of cells visited along the path, including both the start and end cells.

If no valid path exists from start to finish, return -1.

Requirements

1. Both the starting cell (0, 0) and ending cell (n-1, n-1) must be open (have value 0) for any path to exist
2. You can move to any of the 8 adjacent cells (horizontally, vertically, or diagonally) as long as they are open
3. Return the minimum number of cells in any valid path from start to end
4. Return -1 if no path exists

Constraints

• 1 ≤ n ≤ 100
• grid[i][j] is either 0 or 1
• The grid is always square (n × n)
• You cannot revisit cells in the same path

Examples

Example 1:

Input: grid = [[0,1],[0,0]] Output: 3 Explanation: The shortest path is (0,0) → (1,0) → (1,1), which visits 3 cells.

Example 2:

Input: grid = [[0,0,0],[1,1,0],[1,1,0]] Output: 4 Explanation: One shortest path is (0,0) → (0,1) → (1,2) → (2,2), visiting 4 cells.

Example 3:

Input: grid = [[1,0,0],[0,0,0],[0,0,0]] Output: -1 Explanation: The starting cell is blocked, so no path can exist.