Given an N×N binary matrix, return the length of the shortest clear path from the top-left cell to the bottom-right cell.
A clear path can move through cells containing 0 only, and movement is allowed in all 8 directions. Return -1 when no clear path exists.
Example 1
Input: grid = [[0,1],[1,0]]
Output: 2
Explanation: The path moves diagonally from start to destination and visits two cells.
Example 2
Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
Explanation: One shortest clear path visits four cells before reaching the destination.
Approach
Breadth First Search explores the binary matrix level by level from the starting cell. Since every movement has an equal cost, the first removal of the destination from the queue provides the shortest clear-path length.
All eight neighboring cells are examined from every open cell. Marking a cell as visited before queue insertion prevents duplicate entries and ensures single processing.
Algorithm
Return
-1when the starting cell or destination cell is blocked, as no clear path can exist.Initialize a queue with the starting cell and path length
1, since the starting cell contributes to the path length.Mark the starting cell as visited before insertion, preventing repeated queue entries through neighboring cells.
Continue BFS while the queue contains cells and remove the front cell for level-order exploration.
Return the stored path length when the removed cell is the destination, as BFS processes paths in increasing length order.
Examine all eight neighbors and add every in-bounds, open, and unvisited cell with path length increased by
1, marking each cell before insertion.Return
-1when the queue becomes empty without reaching the destination.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds the shortest clear path using BFS. int shortestPathBinaryMatrix(vector<vector<int>>& grid) { int size = grid.size(); // Base case: blocked start or destination makes path impossible. if (grid[0][0] == 1 || grid[size - 1][size - 1] == 1) { return -1; } queue<tuple<int, int, int>> q; // Start BFS from the top-left cell with path length 1. q.push({0, 0, 1}); // Mark the starting cell as visited. grid[0][0] = 1; vector<int> dRow = {-1, -1, -1, 0, 0, 1, 1, 1}; vector<int> dCol = {-1, 0, 1, -1, 1, -1, 0, 1}; // Run BFS across all 8 possible directions. while (!q.empty()) { auto [row, col, dist] = q.front(); q.pop(); // If destination is reached, return the shortest distance. if (row == size - 1 && col == size - 1) { return dist; } // Explore every neighboring cell. for (int dir = 0; dir < 8; dir++) { int nextRow = row + dRow[dir]; int nextCol = col + dCol[dir]; // Check if the next cell is inside the grid. if (nextRow >= 0 && nextCol >= 0 && nextRow < size && nextCol < size) { // Visit only clear and unvisited cells. if (grid[nextRow][nextCol] == 0) { grid[nextRow][nextCol] = 1; q.push({nextRow, nextCol, dist + 1}); } } } } // No path exists after BFS is complete. return -1; }};// Driver code.int main() { vector<vector<int>> grid = { {0, 0, 0}, {1, 1, 0}, {1, 1, 0} }; Solution sol; cout << sol.shortestPathBinaryMatrix(grid); return 0;}Complexity Analysis
Time Complexity: O(N×N), where N is the matrix dimension; every cell enters the queue at most once and checks eight constant-direction neighbors.
Space Complexity: O(N×N), where the visited matrix and BFS queue can each store up to N×N cells.
Interview follow-up Questions
BFS processes cells by path length, so the first destination visit gives the minimum length.
Be the first to add a comment.