Question

16.19. Pond Sizes

中文文档

Description

You have an integer matrix representing a plot of land, where the value at that loca­tion represents the height above sea level. A value of zero indicates water. A pond is a region of water connected vertically, horizontally, or diagonally. The size of the pond is the total number of connected water cells. Write a method to compute the sizes of all ponds in the matrix.

Example:

Input: 

[

  [0,2,1,0],

  [0,1,0,1],

  [1,1,0,1],

  [0,1,0,1]

]

Output:  [1,2,4]

Note:

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

Solutions

Solution 1: DFS

We can traverse each point $(i, j)$ in the integer matrix $land$. If the value of the point is $0$, we start a depth-first search from this point until we reach a point with a non-zero value. The number of points searched during this process is the size of the pond, which is added to the answer array.

Note: To avoid duplicate searches, we set the value of the searched points to $1$.

Finally, we sort the answer array to obtain the final answer.

The time complexity is $O(m \times n \times \log (m \times n))$, and the space complexity is $O(m \times n)$. Here, $m$ and $n$ are the number of rows and columns in the matrix $land$, respectively.

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;
}