Problem
Given an n×n binary matrix, return the length of the shortest clear path from top-left to bottom-right (8-directional movement). Return -1 if none.
Example
Input: [[0,1],[1,0]]
Output: 2Solution
BFS from start. Each step explores 8 neighbors. Mark visited to avoid cycles.
from collections import deque
def shortest_path(grid):
n = len(grid)
if grid[0][0] != 0 or grid[n-1][n-1] != 0: return -1
dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
q = deque([(0, 0, 1)])
grid[0][0] = 1
while q:
r, c, d = q.popleft()
if r == n - 1 and c == n - 1: return d
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
grid[nr][nc] = 1
q.append((nr, nc, d + 1))
return -1function shortestPathBinaryMatrix(grid) {
const n = grid.length;
if (grid[0][0] || grid[n-1][n-1]) return -1;
const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
const q = [[0, 0, 1]];
grid[0][0] = 1;
while (q.length) {
const [r, c, d] = q.shift();
if (r === n - 1 && c === n - 1) return d;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 0) {
grid[nr][nc] = 1;
q.push([nr, nc, d + 1]);
}
}
}
return -1;
}int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
int n = grid.size();
if (grid[0][0] || grid[n-1][n-1]) return -1;
vector<vector<int>> dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
queue<tuple<int,int,int>> q;
q.push({0, 0, 1});
grid[0][0] = 1;
while (!q.empty()) {
auto [r, c, d] = q.front(); q.pop();
if (r == n - 1 && c == n - 1) return d;
for (auto& dir : dirs) {
int nr = r + dir[0], nc = c + dir[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
grid[nr][nc] = 1;
q.push({nr, nc, d + 1});
}
}
}
return -1;
}public int shortestPathBinaryMatrix(int[][] grid) {
int n = grid.length;
if (grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;
int[][] dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{0, 0, 1});
grid[0][0] = 1;
while (!q.isEmpty()) {
int[] curr = q.poll();
int r = curr[0], c = curr[1], d = curr[2];
if (r == n - 1 && c == n - 1) return d;
for (int[] dir : dirs) {
int nr = r + dir[0], nc = c + dir[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
grid[nr][nc] = 1;
q.offer(new int[]{nr, nc, d + 1});
}
}
}
return -1;
}Complexity
- Time: O(n²)
- Space: O(n²)
Explanation
BFS guarantees the first time we reach the destination is via the shortest path. 8-directional means each cell has up to 8 neighbors instead of 4.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?