Leetcode 1091: Shortest Path in Binary Matrix
Given an n x n binary matrix grid, find the shortest clear path in the matrix that connects the top-left cell (0, 0) to the bottom-right cell (n-1, n-1). A clear path is defined as a path where all cells along the path are 0, and the path can move in 8 possible directions (up, down, left, right, and diagonals). Return the length of the shortest clear path, or -1 if no such path exists.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer n representing the size of the grid, followed by an n x n binary matrix `grid`, where each cell contains either a 0 or a 1. A 0 represents a free cell and a 1 represents an obstacle. Additionally, the goal is to find the shortest clear path from the top-left cell (0, 0) to the bottom-right cell (n-1, n-1).
Example: Input: grid = [[0,1],[1,0]]
Constraints:
• 1 <= n <= 100
• grid[i][j] is either 0 or 1
Output: Return the length of the shortest clear path in the grid, or -1 if no such path exists. The path must be clear, with each cell in the path containing 0, and the cells must be connected by 8-directional movement.
Example: Output: 2
Constraints:
• If no clear path exists, return -1.
Goal: To find the shortest path, we use a breadth-first search (BFS) approach, which explores all possible paths and ensures the shortest path is found first.
Steps:
• 1. Initialize a queue with the top-left cell (0, 0) and mark it as visited.
• 2. Use BFS to explore all 8-directional neighbors of each cell.
• 3. If the bottom-right cell (n-1, n-1) is reached, return the length of the path.
• 4. If the queue is empty and the bottom-right cell is not reached, return -1.
Goal: Ensure the solution works within the given grid size and handles both small and large grid cases efficiently.
Steps:
• The grid is square (n x n), with 1 <= n <= 100.
• Each cell contains either 0 or 1, where 0 indicates an empty space and 1 indicates an obstacle.
Assumptions:
• The grid is properly formed with dimensions n x n.
• The pathfinding should consider only cells that contain 0.
• Input: Input: grid = [[0,1],[1,0]]
• Explanation: The grid is a 2x2 matrix. The clear path is from (0, 0) to (1, 1), and the shortest path length is 2, as we move diagonally.
• Input: Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
• Explanation: In this case, the shortest path from (0, 0) to (2, 2) is 4, taking the clear path through (0,0) -> (0,1) -> (1,2) -> (2,2).
• Input: Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
• Explanation: In this case, it's impossible to reach (2, 2) from (0, 0) due to obstacles, so the output is -1.
Approach: We can solve this problem using a breadth-first search (BFS) algorithm, which will explore all possible paths from the top-left to the bottom-right corner while ensuring we always find the shortest path first.
Observations:
• The grid allows movement in 8 directions, which means we need to explore all 8 neighbors at each step.
• We need to ensure that we keep track of visited cells to avoid cycles or reprocessing.
• Using BFS is a natural choice for this problem, as it guarantees finding the shortest path in an unweighted grid.
Steps:
• 1. Initialize a queue with the start position (0, 0) and mark it as visited.
• 2. For each cell, explore all 8 neighboring cells. If a neighbor is valid (within bounds and not visited), mark it as visited and add it to the queue.
• 3. Continue the BFS until the destination (n-1, n-1) is reached or all possible paths are explored.
• 4. If the destination is reached, return the length of the path. If no path is found, return -1.
Empty Inputs:
• If the grid is 1x1, the start and end are the same, and the output is 1 if the cell is 0.
Large Inputs:
• The algorithm should efficiently handle grids as large as 100x100, ensuring that the BFS explores all valid paths without performance issues.
Special Values:
• If the grid has obstacles blocking the entire path, return -1 as no path exists.
Constraints:
• Ensure that the BFS handles both small grids (e.g., 2x2) and large grids (up to 100x100).
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
if(grid[0][0] == 1) return -1;
queue<pair<int, int>> q;
vector<vector<int>> dir = {{0, 1}, {0,-1}, {1, 0}, {1,1}, {1,-1}, {-1,0}, {-1,1}, {-1,-1}};
q.push(make_pair(0,0));
grid[0][0] = 1;
while(!q.empty()) {
auto p = q.front();
int x = p.first, y = p.second;
if(x == m -1 && y == n -1) return grid[x][y];
for(auto d: dir) {
int i = x + d[0], j = y + d[1];
if(i < 0 || j < 0 || i >= m || j >= n || grid[i][j] != 0)
continue;
grid[i][j] = grid[x][y] + 1;
q.push(make_pair(i, j));
}
q.pop();
}
return -1;
}
1 : Function Definition
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
This line defines the function `shortestPathBinaryMatrix` that takes a 2D grid of integers as input and returns an integer representing the shortest path in the matrix.
2 : Variable Initialization - Matrix Dimensions
int m = grid.size(), n = grid[0].size();
This line initializes two variables, `m` and `n`, which store the number of rows and columns of the input grid, respectively.
3 : Edge Case Check
if(grid[0][0] == 1) return -1;
If the starting point (top-left corner) is blocked (value is 1), the function immediately returns -1, indicating that there is no valid path.
4 : Queue Initialization
queue<pair<int, int>> q;
A queue `q` is initialized to store pairs of coordinates representing the current position during the BFS traversal.
5 : Direction Setup
vector<vector<int>> dir = {{0, 1}, {0,-1}, {1, 0}, {1,1}, {1,-1}, {-1,0}, {-1,1}, {-1,-1}};
This vector `dir` stores the possible directions for movement from each cell, including all 8 neighboring cells (up, down, left, right, and diagonals).
6 : Start BFS - Push Initial Position
q.push(make_pair(0,0));
The starting position (0,0) is pushed into the queue to begin the BFS traversal.
7 : Mark Starting Position
grid[0][0] = 1;
The starting position (0,0) is marked as visited by setting its value to 1, indicating that it has been processed.
8 : BFS Loop - Process Queue
while(!q.empty()) {
The while loop starts the BFS process, which continues as long as there are positions in the queue to process.
9 : Queue - Retrieve Front Element
auto p = q.front();
The front element of the queue is retrieved and stored in `p`, representing the current position.
10 : Variable Assignment - Coordinates
int x = p.first, y = p.second;
The coordinates `x` and `y` are extracted from the pair `p`, representing the current cell's position.
11 : Check End Condition
if(x == m -1 && y == n -1) return grid[x][y];
If the current position is the bottom-right corner, the function returns the value of `grid[x][y]`, which represents the length of the shortest path.
12 : Direction Iteration
for(auto d: dir) {
This for loop iterates through each direction in `dir` to check the neighboring cells of the current position.
13 : Neighbor Calculation
int i = x + d[0], j = y + d[1];
The new coordinates `i` and `j` are calculated based on the current position (`x`, `y`) and the direction `d`.
14 : Bounds and Validity Check
if(i < 0 || j < 0 || i >= m || j >= n || grid[i][j] != 0)
This condition checks if the new coordinates are within bounds and whether the cell is unvisited (value 0). If not, it skips to the next direction.
15 : Skip Invalid Cells
continue;
If the neighboring cell is out of bounds or already visited, the loop continues to the next direction.
16 : Mark Neighbor as Visited
grid[i][j] = grid[x][y] + 1;
The neighboring cell is marked as visited by assigning it a value that represents the distance from the starting position.
17 : Push Neighbor to Queue
q.push(make_pair(i, j));
The valid neighboring cell is pushed to the queue for further processing.
18 : Pop Processed Position
q.pop();
After processing all directions for the current position, it is removed from the queue.
19 : Return -1 (No Path Found)
return -1;
If no path is found to the bottom-right corner, the function returns -1.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: The BFS explores each cell at most once, resulting in a time complexity of O(n^2) for an n x n grid.
Best Case: O(n^2)
Worst Case: O(n^2)
Description: The space complexity is O(n^2) due to the need to store the grid and the queue used in BFS.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus