rustgym/leetcode/
_827_making_a_large_island.rs

1struct Solution;
2
3use std::collections::HashMap;
4
5impl Solution {
6    fn largest_island(grid: Vec<Vec<i32>>) -> i32 {
7        let n = grid.len();
8        let mut group = vec![vec![0; n]; n];
9        let mut gid = 0;
10        let mut group_size = vec![0];
11        for i in 0..n {
12            for j in 0..n {
13                if grid[i][j] == 1 && group[i][j] == 0 {
14                    gid += 1;
15                    group_size.push(0);
16                    Self::dfs(i, j, gid, &mut group, &mut group_size, &grid, n);
17                }
18            }
19        }
20        let mut res = *group_size.iter().max().unwrap_or(&0);
21        for i in 0..n {
22            for j in 0..n {
23                if grid[i][j] == 0 {
24                    let mut groups: HashMap<usize, usize> = HashMap::new();
25                    if i > 0 {
26                        let gid = group[i - 1][j];
27                        let size = group_size[gid];
28                        groups.entry(gid).or_insert(size);
29                    }
30                    if j > 0 {
31                        let gid = group[i][j - 1];
32                        let size = group_size[gid];
33                        groups.entry(gid).or_insert(size);
34                    }
35                    if i + 1 < n {
36                        let gid = group[i + 1][j];
37                        let size = group_size[gid];
38                        groups.entry(gid).or_insert(size);
39                    }
40                    if j + 1 < n {
41                        let gid = group[i][j + 1];
42                        let size = group_size[gid];
43                        groups.entry(gid).or_insert(size);
44                    }
45                    res = res.max(groups.values().sum::<usize>() + 1);
46                }
47            }
48        }
49        res as i32
50    }
51
52    fn dfs(
53        i: usize,
54        j: usize,
55        gid: usize,
56        group: &mut Vec<Vec<usize>>,
57        group_size: &mut Vec<usize>,
58        grid: &[Vec<i32>],
59        n: usize,
60    ) {
61        group[i][j] = gid;
62        group_size[gid] += 1;
63        if i > 0 && grid[i - 1][j] == 1 && group[i - 1][j] == 0 {
64            Self::dfs(i - 1, j, gid, group, group_size, grid, n);
65        }
66        if j > 0 && grid[i][j - 1] == 1 && group[i][j - 1] == 0 {
67            Self::dfs(i, j - 1, gid, group, group_size, grid, n);
68        }
69        if i + 1 < n && grid[i + 1][j] == 1 && group[i + 1][j] == 0 {
70            Self::dfs(i + 1, j, gid, group, group_size, grid, n);
71        }
72        if j + 1 < n && grid[i][j + 1] == 1 && group[i][j + 1] == 0 {
73            Self::dfs(i, j + 1, gid, group, group_size, grid, n);
74        }
75    }
76}
77
78#[test]
79fn test() {
80    let grid = vec_vec_i32![[1, 0], [0, 1]];
81    let res = 3;
82    assert_eq!(Solution::largest_island(grid), res);
83    let grid = vec_vec_i32![[1, 1], [1, 0]];
84    let res = 4;
85    assert_eq!(Solution::largest_island(grid), res);
86    let grid = vec_vec_i32![[1, 1], [1, 1]];
87    let res = 4;
88    assert_eq!(Solution::largest_island(grid), res);
89    let grid = vec_vec_i32![[1, 0], [1, 0]];
90    let res = 3;
91    assert_eq!(Solution::largest_island(grid), res);
92}
rustgym/leetcode/_827_making_a_large_island.rs

rustgym/leetcode/
_827_making_a_large_island.rs
