leetcode-rust/src/leetcode/challenge/shortest_path.rs at main · martwz/leetcode-rust · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
use std::collections::{HashSet};
use std::iter::FromIterator;

// 1293. Shortest Path in a Grid with Obstacles Elimination, Hard
// https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/
impl Solution {
    pub fn shortest_path(grid: Vec<Vec<i32>>, k: i32) -> i32 {
        fn bfs(grid: &Vec<Vec<i32>>, pos: (i32, i32), obstacles_left: i32, mut visited: HashSet<(i32, i32)>, paths: &mut Vec<Vec<(i32, i32)>>) {
            let n = grid.len();
            if n == 0 {
                return;
            }
            let m = grid[0].len();

            // reached end?
            if pos.0 == n as i32 - 1 && pos.1 == m as i32 - 1 {
                paths.push(Vec::from_iter(visited));
                return;
            }

            visited.insert((pos.0, pos.1));

            let directions = vec![(0, 1), (0, -1), (1, 0), (-1, 0)];
            for direction in directions {
                let next_pos = (pos.0 + direction.0, pos.1 + direction.1);
                let new_visited = visited.clone();
                // in bounds?
                if next_pos.0 < 0 || next_pos.0 >= n as i32 || next_pos.1 < 0 || next_pos.1 >= m as i32 {
                    continue;
                }
                // not visited?
                if new_visited.contains(&(next_pos.0, next_pos.1)) {
                    continue;
                }

                if grid[next_pos.0 as usize][next_pos.1 as usize] == 1 && obstacles_left > 0 {
                    bfs(grid, next_pos, obstacles_left - 1, new_visited, paths);
                } else if grid[next_pos.0 as usize][next_pos.1 as usize] == 0 {
                    bfs(grid, next_pos, obstacles_left, new_visited, paths);
                }
            }
        }

        let mut paths = Vec::new();

        // start is obstacle?
        if !grid.is_empty() && !grid[0].is_empty() && grid[0][0] == 1 {
            return -1;
        }
        bfs(&grid, (0, 0), k, HashSet::new(), &mut paths);

        paths.sort_by_key(|a| a.len());
        if let Some(path) = paths.first() {
            path.len() as i32
        } else {
            -1
        }
    }
}

struct Solution {}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::vec_vec_i32;

    #[test]
    fn test_shortest_path() {
        assert_eq!(Solution::shortest_path(vec_vec_i32![[0, 0, 0], [1, 1, 0], [0, 0, 0], [0, 1, 1], [0, 0, 0]], 1), 6);
    }

    #[test]
    fn test_shortest_path2() {
        assert_eq!(Solution::shortest_path(vec_vec_i32![[0, 1, 1], [1, 1, 1], [1, 0, 0]], 1), -1);
    }

    #[test]
    fn test_shortest_path3() {
        assert_eq!(Solution::shortest_path(vec_vec_i32![[]], 0), -1);
    }

    #[test]
    fn test_shortest_path4() {
        assert_eq!(Solution::shortest_path(vec_vec_i32![[1]], 0), -1);
    }
}