Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.
A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:
0.The length of a clear path is the number of visited cells of this path.
Example 1:
Input: grid = [[0,1],[1,0]] Output: 2
Example 2:
Input: grid = [[0,0,0],[1,1,0],[1,1,0]] Output: 4
Example 3:
Input: grid = [[1,0,0],[1,1,0],[1,1,0]] Output: -1
Constraints:
n == grid.lengthn == grid[i].length1 <= n <= 100grid[i][j] is 0 or 1This approach involves using BFS to find the shortest path in an unweighted graph. BFS is well-suited for finding the shortest path because it explores all nodes at the present depth prior to moving on to nodes at the next depth level. By maintaining a queue that stores the current cell position and path length, we can efficiently determine the shortest path to the destination. Moreover, since the path can proceed in 8 possible directions, we must consider all potential moves from a given cell.
The function shortestPathBinaryMatrix uses BFS to explore each adjacent cell of the current cell in all 8 possible directions. The grid has been marked to indicate which cells have been visited, avoiding revisiting them and ensuring efficient path finding. If the bottom-right corner is reached, the function returns the path length; otherwise, it returns -1 if no path exists.
C++
Java
Time Complexity: O(n^2) because in the worst case, each cell of the n x n grid is visited once.
Space Complexity: O(n^2) due to the space needed to store the BFS queue.
A* is a popular pathfinding and graph traversal algorithm. It is capable of focusing specifically on the shortest path with the use of heuristics. In this case, the heuristic is the Chebyshev distance between the current cell and the bottom-right corner, which matches the grid's 8-directional movement. By combining the BFS strategy with a heuristic score, A* ensures an efficient pathfinding solution while avoiding unnecessary paths.
This solution deploys the A* algorithm to find the shortest clear path by including a heuristic function, ensuring efficient traversal through the grid by prioritizing paths closer to the end point.
C++
Time Complexity: O(n^2 * log(n)) because each cell is processed once with priority queue operations.
Space Complexity: O(n^2) for the priority queue and grid storage.
| Approach | Complexity |
|---|---|
| Breadth-First Search Approach | Time Complexity: O(n^2) because in the worst case, each cell of the n x n grid is visited once. |
| A* Search Algorithm Approach | Time Complexity: O(n^2 * log(n)) because each cell is processed once with priority queue operations. |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,155 views views
Watch 9 more video solutions →Practice Shortest Path in Binary Matrix with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor