rustgym 0.2.0

rustgym solutions
Documentation 
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

struct Solution;

impl Solution {
    fn contains_cycle(grid: Vec<Vec<char>>) -> bool {
        let n = grid.len();
        let m = grid[0].len();
        let mut visited = vec![vec![false; m]; n];
        for i in 0..n {
            for j in 0..m {
                let c = grid[i][j];
                if Self::dfs(
                    i,
                    j,
                    0,
                    std::usize::MAX,
                    std::usize::MAX,
                    &mut visited,
                    &grid,
                    c,
                    n,
                    m,
                ) {
                    return true;
                }
            }
        }
        false
    }

    fn dfs(
        i: usize,
        j: usize,
        dist: usize,
        pi: usize,
        pj: usize,
        visited: &mut Vec<Vec<bool>>,
        grid: &[Vec<char>],
        c: char,
        n: usize,
        m: usize,
    ) -> bool {
        if dist >= 4 && visited[i][j] {
            return true;
        }
        if visited[i][j] {
            return false;
        }
        visited[i][j] = true;
        if i > 0 && grid[i - 1][j] == c && i - 1 != pi {
            if Self::dfs(i - 1, j, dist + 1, i, j, visited, grid, c, n, m) {
                return true;
            }
        }
        if j > 0 && grid[i][j - 1] == c && j - 1 != pj {
            if Self::dfs(i, j - 1, dist + 1, i, j, visited, grid, c, n, m) {
                return true;
            }
        }
        if i + 1 < n && grid[i + 1][j] == c && i + 1 != pi {
            if Self::dfs(i + 1, j, dist + 1, i, j, visited, grid, c, n, m) {
                return true;
            }
        }
        if j + 1 < m && grid[i][j + 1] == c && j + 1 != pj {
            if Self::dfs(i, j + 1, dist + 1, i, j, visited, grid, c, n, m) {
                return true;
            }
        }
        false
    }
}

#[test]
fn test() {
    let grid = vec_vec_char![
        ['a', 'a', 'a', 'a'],
        ['a', 'b', 'b', 'a'],
        ['a', 'b', 'b', 'a'],
        ['a', 'a', 'a', 'a']
    ];
    let res = true;
    assert_eq!(Solution::contains_cycle(grid), res);
    let grid = vec_vec_char![
        ['c', 'c', 'c', 'a'],
        ['c', 'd', 'c', 'c'],
        ['c', 'c', 'e', 'c'],
        ['f', 'c', 'c', 'c']
    ];
    let res = true;
    assert_eq!(Solution::contains_cycle(grid), res);
    let grid = vec_vec_char![['a', 'b', 'b'], ['b', 'z', 'b'], ['b', 'b', 'a']];
    let res = false;
    assert_eq!(Solution::contains_cycle(grid), res);
    let grid = vec_vec_char![
        ['c', 'a', 'd'],
        ['a', 'a', 'a'],
        ['a', 'a', 'd'],
        ['a', 'c', 'd'],
        ['a', 'b', 'c']
    ];
    let res = true;
    assert_eq!(Solution::contains_cycle(grid), res);
    let grid = vec_vec_char![
        ['b', 'a', 'c'],
        ['c', 'a', 'c'],
        ['d', 'd', 'c'],
        ['b', 'c', 'c']
    ];
    let res = false;
    assert_eq!(Solution::contains_cycle(grid), res);
}