LeetCode_DFS_中等_面试题 16.19.水域大小

迈不过友情╰ 2023-10-12 19:23 18阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

## 2.思路 ##

（1）DFS  
本题与[200.岛屿数量][200.]这题十分类似，只不过在其基础之上要统计水域的大小即可。

## 3.代码实现（Java） ##

//思路1————DFS
    class Solution {
        
    
        int m;
        int n;
    
        public int[] pondSizes(int[][] land) {
        
            m = land.length;
            n = land[0].length;
            List<Integer> resList = new ArrayList<>();
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (land[i][j] == 0) {
        
                        resList.add(dfs(land, i, j));
                    }
                }
            }
            int[] res = new int[resList.size()];
            for (int i = 0; i < resList.size(); i++) {
        
                res[i] = resList.get(i);
            }
            Arrays.sort(res);
            return res;
        }
    
        private int dfs(int[][] land, int x, int y) {
        
            if (x < 0 || y < 0 || x >= m || y >= n || land[x][y] != 0) {
        
                return 0;
            }
            land[x][y] = -1;
            int res = 1;
            for (int dx = -1; dx <= 1; dx++) {
        
                for (int dy = -1; dy <= 1; dy++) {
        
                    if (dx == 0 && dy == 0) {
        
                        continue;
                    }
                    res += dfs(land, x + dx, y + dy);
                }
            }
            return res;
        }
    }

[200.]: https://blog.csdn.net/weixin_43004044/article/details/124337167