106 lines
2.8 KiB
Rust
106 lines
2.8 KiB
Rust
use std::collections::VecDeque;
|
|
use std::convert::TryInto;
|
|
|
|
struct Solution {}
|
|
impl Solution {
|
|
pub fn shortest_path_binary_matrix(grid: Vec<Vec<i32>>) -> i32 {
|
|
let n = grid.len();
|
|
|
|
// create an array of distances
|
|
let mut distances = grid.clone();
|
|
for y in 0..n {
|
|
for x in 0..n {
|
|
distances[y][x] = -1;
|
|
}
|
|
}
|
|
|
|
// initialize the start with an initial distance
|
|
let mut q: VecDeque<(usize, usize)> = VecDeque::new();
|
|
if grid[0][0] == 0 {
|
|
distances[0][0] = 1;
|
|
q.push_back((0, 0));
|
|
}
|
|
|
|
while let Some((y, x)) = q.pop_front() {
|
|
if (y, x) == (n - 1, n - 1) {
|
|
break;
|
|
}
|
|
|
|
for (next_y, next_x) in (-1_isize..=1)
|
|
.flat_map(|dy| (-1_isize..=1).map(move |dx| (dy, dx)))
|
|
.map(|(dy, dx)| (y as isize + dy, x as isize + dx))
|
|
.filter(|&(next_y, next_x)| {
|
|
(next_y, next_x) != (y as isize, x as isize)
|
|
&& next_y >= 0
|
|
&& next_y < n.try_into().unwrap()
|
|
&& next_x >= 0
|
|
&& next_x < n.try_into().unwrap()
|
|
})
|
|
{
|
|
let (next_y, next_x) = (next_y as usize, next_x as usize);
|
|
|
|
if distances[next_y][next_x] == -1 && grid[next_y][next_x] == 0 {
|
|
distances[next_y][next_x] = distances[y][x] + 1;
|
|
q.push_back((
|
|
(next_y as isize).try_into().unwrap(),
|
|
(next_x as isize).try_into().unwrap(),
|
|
));
|
|
}
|
|
}
|
|
}
|
|
|
|
distances[n - 1][n - 1]
|
|
}
|
|
}
|
|
|
|
fn main() {
|
|
assert_eq!(
|
|
Solution::shortest_path_binary_matrix(vec![vec![0, 1], vec![1, 0]]),
|
|
2
|
|
);
|
|
assert_eq!(
|
|
Solution::shortest_path_binary_matrix(vec![vec![0, 0, 0], vec![1, 1, 0], vec![1, 1, 0]]),
|
|
4
|
|
);
|
|
assert_eq!(
|
|
Solution::shortest_path_binary_matrix(vec![vec![1, 0, 0], vec![1, 1, 0], vec![1, 1, 0]]),
|
|
-1
|
|
);
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod tests {
|
|
use super::*;
|
|
|
|
#[test]
|
|
fn example_1() {
|
|
assert_eq!(
|
|
Solution::shortest_path_binary_matrix(vec![vec![0, 1], vec![1, 0]]),
|
|
2
|
|
);
|
|
}
|
|
|
|
#[test]
|
|
fn example_2() {
|
|
assert_eq!(
|
|
Solution::shortest_path_binary_matrix(vec![
|
|
vec![0, 0, 0],
|
|
vec![1, 1, 0],
|
|
vec![1, 1, 0]
|
|
]),
|
|
4
|
|
);
|
|
}
|
|
|
|
#[test]
|
|
fn example_3() {
|
|
assert_eq!(
|
|
Solution::shortest_path_binary_matrix(vec![
|
|
vec![1, 0, 0],
|
|
vec![1, 1, 0],
|
|
vec![1, 1, 0]
|
|
]),
|
|
-1
|
|
);
|
|
}
|
|
}
|