Shortest Path in Binary Matrix
Given an n x n binary matrix, return the length of the shortest clear path from top-left to bottom-right. A clear path visits only 0-cells and moves in 8 directions. Return -1 if no path.
Input: n rows of comma-separated 0/1.
Example:
0,1 1,0
2
- The input is a 2×2 binary matrix:
0,1 1,0 - We start at the top-left cell (0) and explore neighboring cells in 8 directions, finding a clear path to the bottom-right cell (0) in 2 steps: right and down are blocked, so we go right then down, or down then right, but since the direct path is blocked by a 1, we consider diagonal moves and find that moving diagonally is not an option here, instead we move in an L-shape.
- The shortest clear path has a length of 2 since we move in an L-shape: right then down, or down then right, but due to the 1-cell, the path is not completely straight.
- The final output is 2.
Constraints:
- 1 <= n <= 100
- grid[i][j] is 0 or 1
Background Knowledge
The problem involves finding the shortest path in a binary matrix, which is a fundamental concept in graph theory. A binary matrix is a 2D array of 0s and 1s, where 0 represents a clear cell and 1 represents a blocked cell. The goal is to find the shortest path from the top-left cell to the bottom-right cell, moving in 8 possible directions (up, down, left, right, and 4 diagonals). This problem can be modeled as a graph, where each cell is a node, and two nodes are connected if the corresponding cells are adjacent and clear.
To solve this problem, you need to understand the basics of graph traversal algorithms, such as Breadth-First Search (BFS) and Depth-First Search (DFS). BFS is particularly useful for finding the shortest path in an unweighted graph, as it explores all nodes at a given distance before moving on to the next distance level. You should also be familiar with the concept of queue data structure, which is often used to implement BFS algorithms.
In the context of this problem, you can think of the binary matrix as a grid graph, where each cell is a node, and the edges represent the possible movements between cells. The shortest path can be found by exploring the grid graph using a BFS algorithm, keeping track of the distance from the starting node (top-left cell) to each visited node.
Algorithm/Approach
The general approach to solve this problem involves using a Breadth-First Search (BFS) algorithm to explore the grid graph. The BFS algorithm will help you find the shortest path from the top-left cell to the bottom-right cell by exploring all possible paths level by level. You will need to use a queue data structure to keep track of the nodes to be visited and their corresponding distances from the starting node.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.