1091. Shortest Path in Binary Matrix

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[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. `1 <= grid.length == grid[0].length <= 100`
2. `grid[r][c]` is `0` or `1`

1091. Shortest Path in Binary Matrix
``````struct Solution;
use std::collections::VecDeque;

type Point = (usize, usize);

impl Solution {
fn shortest_path_binary_matrix(grid: Vec<Vec<i32>>) -> i32 {
let n = grid.len();
let m = grid[0].len();
let mut queue: VecDeque<Point> = VecDeque::new();
if grid[0][0] == 1 || grid[(n - 1) as usize][(m - 1) as usize] == 1 {
return -1;
}
let mut visited: Vec<Vec<bool>> = vec![vec![false; m]; n];
visited[0][0] = true;
queue.push_back((0, 0));
let mut distance = 0;
let offsets = [
(-1, -1),
(0, -1),
(1, -1),
(-1, 1),
(0, 1),
(1, 1),
(-1, 0),
(1, 0),
];
while !queue.is_empty() {
distance += 1;
let queue_size = queue.len();
for _ in 0..queue_size {
let p = queue.pop_front().unwrap();
if p.0 == n - 1 && p.1 == m - 1 {
return distance;
} else {
for offset in &offsets {
let x = p.0 as i32 + offset.0;
let y = p.1 as i32 + offset.1;
if !(x < 0 || x >= n as i32 || y < 0 || y >= m as i32)
&& grid[x as usize][y as usize] == 0
&& !visited[x as usize][y as usize]
{
visited[x as usize][y as usize] = true;
queue.push_back((x as usize, y as usize));
}
}
}
}
}
-1
}
}

#[test]
fn test() {
let grid = vec_vec_i32![[0, 1], [1, 0]];
let res = 2;
assert_eq!(Solution::shortest_path_binary_matrix(grid), res);
let grid = vec_vec_i32![[0, 0, 0], [1, 1, 0], [1, 1, 0]];
let res = 4;
assert_eq!(Solution::shortest_path_binary_matrix(grid), res);
let grid = vec_vec_i32![[1, 0, 0], [1, 1, 0], [1, 1, 0]];
let res = -1;
assert_eq!(Solution::shortest_path_binary_matrix(grid), res);
let grid = vec_vec_i32![
[0, 1, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 1, 1],
[0, 1, 0, 0, 0, 1],
[1, 0, 0, 1, 0, 1],
[0, 0, 1, 0, 1, 0]
];
let res = 7;
assert_eq!(Solution::shortest_path_binary_matrix(grid), res);
}
``````