水域大小(Java)

水域大小(Java)

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

package com.loo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PondAreaSize {
    // 当前坐标对应的八个方向
    public static int[] dirX = new int[] {0 , 1 , 1 , 1 , 0 , -1 , -1 , -1};
    public static int[] dirY = new int[] {1 , 1 , 0 , -1 , -1 , -1 , 0 , 1};

    public static void main(String[] args) {
        int[][] land = new int[][] {
                {0,2,1,0},
                {0,1,0,1},
                {1,1,0,1},
                {0,1,0,1}
        };
        Integer[] pondArea = getPondAreaSize(land);
        System.out.String(pondArea));
    }
    
    public static Integer[] getPondAreaSize(int[][] pond) {
        int count = 0;
        List<Integer> list = new ArrayList<Integer>();
        for (int i=0;i<pond.length;i++) {
            for (int j=0;j<pond[0].length;j++) {
                count = findRoundPond(pond , i , j);
                if (count!=0) {
                    list.add(count);
                }
            }
        }
        Integer[] result = Array(new Integer[list.size()]);
        Arrays.sort(result);
        return result;
    }
    // 遍历矩阵，遇到0之后就开始搜索周围是否还有0，搜索过程递归的返回条件就是pond[x][y] != 0或索引x和y越界。
        // 为了避免在递归的时候重复判断矩阵中的0，因为在判断池塘个数的过程中，每个0只会被记录一次，记录完之后就没有价值了，所以可以在判断为0后加上pond[x][y] = -1，这样在下次dfs的时候就可以避免重复的0。
    public static int findRoundPond(int[][] pond , int x , int y) {
        int count = 0;
        if (x<0 || x>=pond.length || y<0 || y>=pond[0].length || pond[x][y]!=0) {
            return count;
        }
        count++;
        pond[x][y] = -1;
        for (int i=0;i<dirX.length;i++) {
            int dx = x + dirX[i];
            int dy = y + dirY[i];
            count += findRoundPond(pond , dx , dy);
        }
        return count;
    }

}