1
2
3
4
5
6

输入:
11110
11010
11000
00000
输出: 1

1
2
3
4
5
6
7

输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

 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

struct Solution;

// @lc code=start

struct UnionFindSet {
    n: usize,
    pa: Vec<usize>,
}

impl UnionFindSet {
    pub fn new(n: usize) -> Self {
        UnionFindSet{
            n,
            pa: (0..n).collect::<Vec<_>>(),
        }
    }

    pub fn size(&self) -> usize {
        self.n
    }

    pub fn find(&mut self, a: usize) -> usize {
        let mut a_ = a;
        while self.pa[a_] != a_ {
            a_ = self.pa[a_];
        }
        self.pa[a] = a_;

        a_
    }

    pub fn union(&mut self, a: usize, b: usize) {
        let (a_, b_) = (self.find(a), self.find(b));
        if a_ != b_ {
            self.pa[a_] = b_;
            self.n -= 1;
        }
    }
}

impl Solution {
    /// ## 解题思路
    /// - 并查集
    pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
        let (m, n) = (grid.len(), grid[0].len());
        let mut water = 0_i32;
        let mut ufs = UnionFindSet::new(m*n);
        for i in 0..m {
            for j in 0..n {
                if grid[i][j] == '0' {
                    water += 1;
                    continue;
                }
                [(0, 1), (0, !0), (1, 0), (!0, 0)]
                    .iter()
                    .map(|&d| (i.wrapping_add(d.0), j.wrapping_add(d.1)))
                    .filter(|(di, dj)| (0..m).contains(di) && (0..n).contains(dj))
                    .filter(|(di, dj)| grid[*di][*dj] == '1')
                    .for_each(|(di, dj)|{
                        ufs.union(di*n+dj, i*n+j);
                    });
            }
        }

        ufs.size() as i32 - water
    }
}
// @lc code=end

 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

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = m ? grid[0].size() : 0;
        int islands = 0;
        for (int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(grid[i][j] == '1') {
                    islands++;
                    eraseIslands(grid, i, j);
                }
            }
        }
        return islands;
    }

private:
    void eraseIslands(vector<vector<char>>& grid, int i, int j) {
        int m = grid.size();
        int n = grid[0].size();
        if (i<0 || i==m || j<0 || j==n || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';

        eraseIslands(grid, i-1, j);
        eraseIslands(grid, i+1, j);
        eraseIslands(grid, i, j-1);
        eraseIslands(grid, i, j+1);
    }
};