rustgym/leetcode/
_1559_detect_cycles_in_2d_grid.rs

1struct Solution;
2
3impl Solution {
4    fn contains_cycle(grid: Vec<Vec<char>>) -> bool {
5        let n = grid.len();
6        let m = grid[0].len();
7        let mut visited = vec![vec![false; m]; n];
8        for i in 0..n {
9            for j in 0..m {
10                let c = grid[i][j];
11                if Self::dfs(
12                    i,
13                    j,
14                    0,
15                    std::usize::MAX,
16                    std::usize::MAX,
17                    &mut visited,
18                    &grid,
19                    c,
20                    n,
21                    m,
22                ) {
23                    return true;
24                }
25            }
26        }
27        false
28    }
29
30    fn dfs(
31        i: usize,
32        j: usize,
33        dist: usize,
34        pi: usize,
35        pj: usize,
36        visited: &mut Vec<Vec<bool>>,
37        grid: &[Vec<char>],
38        c: char,
39        n: usize,
40        m: usize,
41    ) -> bool {
42        if dist >= 4 && visited[i][j] {
43            return true;
44        }
45        if visited[i][j] {
46            return false;
47        }
48        visited[i][j] = true;
49        if i > 0 && grid[i - 1][j] == c && i - 1 != pi {
50            if Self::dfs(i - 1, j, dist + 1, i, j, visited, grid, c, n, m) {
51                return true;
52            }
53        }
54        if j > 0 && grid[i][j - 1] == c && j - 1 != pj {
55            if Self::dfs(i, j - 1, dist + 1, i, j, visited, grid, c, n, m) {
56                return true;
57            }
58        }
59        if i + 1 < n && grid[i + 1][j] == c && i + 1 != pi {
60            if Self::dfs(i + 1, j, dist + 1, i, j, visited, grid, c, n, m) {
61                return true;
62            }
63        }
64        if j + 1 < m && grid[i][j + 1] == c && j + 1 != pj {
65            if Self::dfs(i, j + 1, dist + 1, i, j, visited, grid, c, n, m) {
66                return true;
67            }
68        }
69        false
70    }
71}
72
73#[test]
74fn test() {
75    let grid = vec_vec_char![
76        ['a', 'a', 'a', 'a'],
77        ['a', 'b', 'b', 'a'],
78        ['a', 'b', 'b', 'a'],
79        ['a', 'a', 'a', 'a']
80    ];
81    let res = true;
82    assert_eq!(Solution::contains_cycle(grid), res);
83    let grid = vec_vec_char![
84        ['c', 'c', 'c', 'a'],
85        ['c', 'd', 'c', 'c'],
86        ['c', 'c', 'e', 'c'],
87        ['f', 'c', 'c', 'c']
88    ];
89    let res = true;
90    assert_eq!(Solution::contains_cycle(grid), res);
91    let grid = vec_vec_char![['a', 'b', 'b'], ['b', 'z', 'b'], ['b', 'b', 'a']];
92    let res = false;
93    assert_eq!(Solution::contains_cycle(grid), res);
94    let grid = vec_vec_char![
95        ['c', 'a', 'd'],
96        ['a', 'a', 'a'],
97        ['a', 'a', 'd'],
98        ['a', 'c', 'd'],
99        ['a', 'b', 'c']
100    ];
101    let res = true;
102    assert_eq!(Solution::contains_cycle(grid), res);
103    let grid = vec_vec_char![
104        ['b', 'a', 'c'],
105        ['c', 'a', 'c'],
106        ['d', 'd', 'c'],
107        ['b', 'c', 'c']
108    ];
109    let res = false;
110    assert_eq!(Solution::contains_cycle(grid), res);
111}
rustgym/leetcode/_1559_detect_cycles_in_2d_grid.rs

rustgym/leetcode/
_1559_detect_cycles_in_2d_grid.rs
