Solution3.rs

const DIRS: [usize; 3] = [1, 0, 1];

impl Solution {
    pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut p: Vec<i32> = (0..(m * n) as i32).collect();

        fn find(p: &mut Vec<i32>, x: usize) -> i32 {
            if p[x] != (x as i32) {
                p[x] = find(p, p[x] as usize);
            }
            p[x]
        }

        for i in 0..m {
            for j in 0..n {
                if grid[i][j] == '1' {
                    for k in 0..2 {
                        let x = i + DIRS[k];
                        let y = j + DIRS[k + 1];
                        if x < m && y < n && grid[x][y] == '1' {
                            let f1 = find(&mut p, x * n + y);
                            let f2 = find(&mut p, i * n + j);
                            p[f1 as usize] = f2;
                        }
                    }
                }
            }
        }

        let mut ans = 0;
        for i in 0..m {
            for j in 0..n {
                if grid[i][j] == '1' && p[i * n + j] == ((i * n + j) as i32) {
                    ans += 1;
                }
            }
        }
        ans
    }
}