面试题16.19.水域大小

链接：面试题16.19.水域大小
难度：Medium
标签：深度优先搜索、广度优先搜索、并查集、数组、矩阵
简介：你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。

题解 1 - cpp

• 编辑时间：2023-06-22
• 执行用时：8ms
• 内存消耗：11.4MB
• 编程语言：cpp
• 解法介绍：bfs。

#define X first
#define Y second
#define pii pair<int, int>
vector<vector<int>> dirs2 = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
class Solution {
public:
    vector<int> pondSizes(vector<vector<int>>& land) {
        int n = land.size(), m = land[0].size(), used[n][m];
        memset(used, 0, sizeof(used));
        vector<int> res;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!used[i][j] && land[i][j] == 0) {
                    used[i][j] = 1;
                    queue<pii> q;
                    q.push(make_pair(i, j));
                    int cnt = 1;
                    while (q.size()) {
                        auto cur = q.front();
                        q.pop();
                        for (auto &dir : dirs2) {
                            int ni = cur.X + dir[0], nj = cur.Y + dir[1];
                            if (0 <= ni && ni < n && 0 <= nj && nj < m && land[ni][nj] == 0 && !used[ni][nj]) {
                                cnt += 1;
                                used[ni][nj] = 1;
                                q.push(make_pair(ni, nj));
                            }
                        }
                    }
                    res.push_back(cnt);
                }
            }
        }
        sort(res.begin(), res.end());
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-06-22
• 执行用时：204ms
• 内存消耗：27.5MB
• 编程语言：python
• 解法介绍：同上。

dirs2 = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    class Solution:
        def pondSizes(self, land: List[List[int]]) -> List[int]:
            n = len(land)
            m = len(land[0])
            used = [[False for _ in range(m)] for _ in range(n)]
            res = []
            for i in range(n):
                for j in range(m):
                    if not used[i][j] and land[i][j] == 0:
                        used[i][j] = True
                        q = deque()
                        q.append((i, j))
                        cnt = 1
                        while len(q):
                            cur = q.popleft()
                            for dir in dirs2:
                                ni = cur[0] + dir[0]
                                nj = cur[1] + dir[1]
                                if 0 <= ni < n and 0 <= nj < m and land[ni][nj] == 0 and not used[ni][nj]:
                                    cnt += 1
                                    used[ni][nj] = True
                                    q.append((ni, nj))
                        res.append(cnt)
            res.sort()
            return res

题解 3 - rust

• 编辑时间：2023-06-22
• 执行用时：16ms
• 内存消耗：4MB
• 编程语言：rust
• 解法介绍：同上。

pub const dirs2: [[i32; 2]; 8] = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]];
impl Solution {
    pub fn pond_sizes(land: Vec<Vec<i32>>) -> Vec<i32> {
        let n = land.len();
        let m = land[0].len();
        let mut used = vec![vec![false; m]; n];
        let mut res = vec![];
        for i in 0..n {
            for j in 0..m {
                if !used[i][j] && land[i][j] == 0 {
                    used[i][j] = true;
                    let mut q = std::collections::VecDeque::<(usize, usize)>::new();
                    q.push_back((i, j));
                    let mut cnt = 1;
                    while !q.is_empty() {
                        let (i, j) = q.pop_front().unwrap();
                        for dir in dirs2 {
                            let ni = i as i32 + dir[0];
                            let nj = j as i32 + dir[1];
                            if 0 <= ni
                                && ni < n as i32
                                && 0 <= nj
                                && nj < m as i32
                                && land[ni as usize][nj as usize] == 0
                                && !used[ni as usize][nj as usize]
                            {
                                let ni = ni as usize;
                                let nj = nj as usize;
                                cnt += 1;
                                used[ni][nj] = true;
                                q.push_back((ni, nj));
                            }
                        }
                    }
                    res.push(cnt);
                }
            }
        }
        res.sort();
        res
    }
}