# Shortest Path in Binary Matrix

0
3378

Today, we will practice on a popular algorithm question, which is questioned by many top companies in recent, it is to find shortest path in binary matrix.

Article Contents

### Problem

In an N by N square grid, each cell is either empty (0) or blocked (1).

clear path from top-left to bottom-right has length `k` if and only if it is composed of cells `C_1, C_2, ..., C_k` such that:

• Adjacent cells `C_i` and `C_{i+1}` are connected 8-directionally (ie., they are different and share an edge or corner)
• `C_1` is at location `(0, 0)` (ie. has value `grid`)
• `C_k` is at location `(N-1, N-1)` (ie. has value `grid[N-1][N-1]`)
• If `C_i` is located at `(r, c)`, then `grid[r][c]` is empty (ie. `grid[r][c] == 0`).

Return the length of the shortest such clear path from top-left to bottom-right.  If such a path does not exist, return -1.

Examples:

``````Example 1:
Input: [[0,1],[1,0]]
Output: 2
Explanation: move from [0,0] to [1,1].

Example 2:
Input: [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
Explanation: the shortest path is [0,0] [0,1] [1,2] [2,2].

``````

### Analysis

To scan a matrix, we can use either DFS or BFS to solve it. However, if we use DFS, we need to go through all possible paths in order to find out which one is the shortest.

If we use BFS, in each step, we need to decide which one would move into bottom right position first.

Comparing the two, we can see BFS make more sense than DFS, and probably easier to implement.

### Solution

The solution is written in Java.

``````public int shortestPathBinaryMatrix(int[][] grid) {
int n = grid.length;

// unreachable path
if (grid != 0 || grid[n-1][n-1] != 0) return -1;

Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {0, 0}); // starting top-left
int steps = 0;

while (!queue.isEmpty()) {
int size = queue.size();
steps++;
for (int t = 0; t < size; t++) {
int[] cell = queue.poll();
int r = cell, c = cell;

if (r == n - 1 && c == n - 1) return steps; // reach bottom-right

for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
int nr = r + i, nc = c + j;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
queue.offer(new int[] {nr, nc});
grid[nr][nc] = -1; // mark as visited
}
}
}
}
}
return -1;
}``````