Question

面试题 16.19. 水域大小

English Version

题目描述

你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。

示例：

输入：
[
  [0,2,1,0],
  [0,1,0,1],
  [1,1,0,1],
  [0,1,0,1]
]
输出： [1,2,4]

提示：

• 0 < len(land) <= 1000
• 0 < len(land[i]) <= 1000

解法

方法一：DFS

我们可以遍历整数矩阵 $land$ 中的每个点 $(i, j)$，如果该点的值为 $0$，则从该点开始进行深度优先搜索，直到搜索到的点的值不为 $0$，则停止搜索，此时搜索到的点的个数即为池塘的大小，将其加入答案数组中。

注意：在进行深度优先搜索时，为了避免重复搜索，我们将搜索到的点的值置为 $1$。

最后，我们对答案数组进行排序，即可得到最终答案。

时间复杂度 $O(m \times n \times \log (m \times n))，空间复杂度 O(m \times n)$。其中 $m$ 和 $n$ 分别为矩阵 $land$ 的行数和列数。

class Solution:
  def pondSizes(self, land: List[List[int]]) -> List[int]:
    def dfs(i: int, j: int) -> int:
      res = 1
      land[i][j] = 1
      for x in range(i - 1, i + 2):
        for y in range(j - 1, j + 2):
          if 0 <= x < m and 0 <= y < n and land[x][y] == 0:
            res += dfs(x, y)
      return res

    m, n = len(land), len(land[0])
    return sorted(dfs(i, j) for i in range(m) for j in range(n) if land[i][j] == 0)

class Solution {
  private int m;
  private int n;
  private int[][] land;

  public int[] pondSizes(int[][] land) {
    m = land.length;
    n = land[0].length;
    this.land = land;
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (land[i][j] == 0) {
          ans.add(dfs(i, j));
        }
      }
    }
    return ans.stream().sorted().mapToInt(Integer::valueOf).toArray();
  }

  private int dfs(int i, int j) {
    int res = 1;
    land[i][j] = 1;
    for (int x = i - 1; x <= i + 1; ++x) {
      for (int y = j - 1; y <= j + 1; ++y) {
        if (x >= 0 && x < m && y >= 0 && y < n && land[x][y] == 0) {
          res += dfs(x, y);
        }
      }
    }
    return res;
  }
}

class Solution {
public:
  vector<int> pondSizes(vector<vector<int>>& land) {
    int m = land.size(), n = land[0].size();
    function<int(int, int)> dfs = [&](int i, int j) -> int {
      int res = 1;
      land[i][j] = 1;
      for (int x = i - 1; x <= i + 1; ++x) {
        for (int y = j - 1; y <= j + 1; ++y) {
          if (x >= 0 && x < m && y >= 0 && y < n && land[x][y] == 0) {
            res += dfs(x, y);
          }
        }
      }
      return res;
    };
    vector<int> ans;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (land[i][j] == 0) {
          ans.push_back(dfs(i, j));
        }
      }
    }
    sort(ans.begin(), ans.end());
    return ans;
  }
};

func pondSizes(land [][]int) (ans []int) {
  m, n := len(land), len(land[0])
  var dfs func(i, j int) int
  dfs = func(i, j int) int {
    res := 1
    land[i][j] = 1
    for x := i - 1; x <= i+1; x++ {
      for y := j - 1; y <= j+1; y++ {
        if x >= 0 && x < m && y >= 0 && y < n && land[x][y] == 0 {
          res += dfs(x, y)
        }
      }
    }
    return res
  }
  for i := range land {
    for j := range land[i] {
      if land[i][j] == 0 {
        ans = append(ans, dfs(i, j))
      }
    }
  }
  sort.Ints(ans)
  return
}

function pondSizes(land: number[][]): number[] {
  const m = land.length;
  const n = land[0].length;
  const dfs = (i: number, j: number): number => {
    let res = 1;
    land[i][j] = 1;
    for (let x = i - 1; x <= i + 1; ++x) {
      for (let y = j - 1; y <= j + 1; ++y) {
        if (x >= 0 && x < m && y >= 0 && y < n && land[x][y] === 0) {
          res += dfs(x, y);
        }
      }
    }
    return res;
  };
  const ans: number[] = [];
  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; ++j) {
      if (land[i][j] === 0) {
        ans.push(dfs(i, j));
      }
    }
  }
  ans.sort((a, b) => a - b);
  return ans;
}