Formatted question description: https://leetcode.ca/all/1091.html

# 1091. Shortest Path in Binary Matrix

## Level

Medium

## Description

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

A *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[0][0]`

)`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.

**Example 1:**

**Input:** [[0,1],[1,0]]

**Output:** 2

**Example 2:**

**Input:** [[0,0,0],[1,1,0],[1,1,0]]

**Output:** 4

**Note:**

`1 <= grid.length == grid[0].length <= 100`

`grid[r][c]`

is`0`

or`1`

## Solution

If `grid`

has 0 rows or 0 columns, then such a path does not exist. Also if the top-left corner of `grid`

is blocked or the bottom-right corner of `grid`

is blocked, then such a path does not exist. In these cases, return -1.

Use breadth first search to find the length of the shortest path. The top-left corner has path length 1. Starting from the top-left corner, search all adjacent cells that are connected 8-directionally. If an adjacent cell is empty and not visited, update the distance of the adjacent cell and add it to the queue for further search.

If the bottom-right corner can be reached, return the length of the shortest path. Otherwise, return -1.

```
class Solution {
public int shortestPathBinaryMatrix(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0)
return -1;
int side = grid.length;
if (grid[0][0] == 1 || grid[side - 1][side - 1] == 1)
return -1;
final int BLOCK = -1;
final int WHITE = 0;
final int GRAY = 1;
final int BLACK = 2;
int[][] colors = new int[side][side];
int[][] distances = new int[side][side];
for (int i = 0; i < side; i++) {
for (int j = 0; j < side; j++) {
if (grid[i][j] == 0) {
colors[i][j] = WHITE;
distances[i][j] = Integer.MAX_VALUE;
} else {
colors[i][j] = BLOCK;
distances[i][j] = -1;
}
}
}
colors[0][0] = GRAY;
distances[0][0] = 1;
int[][] directions = { {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1} };
Queue<int[]> queue = new LinkedList<int[]>();
queue.offer(new int[]{0, 0});
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int row = cell[0], column = cell[1];
int distance = distances[row][column];
for (int[] direction : directions) {
int newRow = row + direction[0], newColumn = column + direction[1];
if (newRow >= 0 && newRow < side && newColumn >= 0 && newColumn < side && colors[newRow][newColumn] == WHITE) {
colors[newRow][newColumn] = GRAY;
distances[newRow][newColumn] = distance + 1;
queue.offer(new int[]{newRow, newColumn});
}
}
colors[row][column] = BLACK;
}
return distances[side - 1][side - 1] == Integer.MAX_VALUE ? -1 : distances[side - 1][side - 1];
}
}
```