gold-16-19

你有一个用于表示一片土地的整数矩阵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

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    private int curV = 0;

    public int[] pondSizes(int[][] land) {
        for (int i = 0; i < land.length; i++) {
            for (int j = 0; j < land[i].length; j++) {
                if (land[i][j] == 0) {
                    curV--;
                    findNext(land, i, j);
                }
            }
        }

        int[] arr = new int[-curV];
        for (int i = 0; i < land.length; i++) {
            for (int j = 0; j < land[i].length; j++) {
                if (land[i][j] < 0) {
                    arr[-land[i][j] - 1]++;
                }
            }
        }

        Arrays.sort(arr);
        return arr;
    }

    private void findNext(int[][] land, int r, int c) {
        if (land[r][c] != 0) {
            return;
        }

        land[r][c] = curV;

        if (r < land.length - 1) {
            findNext(land, r + 1, c);
        }
        if (c < land[0].length - 1) {
            findNext(land, r, c + 1);
        }
        if (r > 0) {
            findNext(land, r - 1, c);
        }
        if (c > 0) {
            findNext(land, r, c - 1);
        }

        if (r > 0 &&  c < land[0].length - 1) {
            findNext(land, r - 1, c + 1);
        }
        if (r < land.length - 1 && c < land[0].length - 1) {
            findNext(land, r + 1, c + 1);
        }
        if (r < land.length - 1 && c > 0) {
            findNext(land, r + 1, c - 1);
        }
        if (r > 0 && c > 0) {
            findNext(land, r - 1, c - 1);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)