Problem: 面试题 16.19. 水域大小

题目描述

思路

该问题可以归纳为一类遍历二维矩阵的题目，此类中的一部分题目可以利用DFS来解决，具体到本题目（该题目可以的写法大体不变可参看前面几个题目：）：

Problem: 力扣面试题 08.10. 颜色填充（java DFS解法）
Problem: 力扣200. 岛屿数量（java DFS解法）
Problem: 力扣LCR 130. 衣橱整理（DFS 解法）

具体到本题目中：

我们只需要将记录方位的数组扩展成记录上、下、左、右、左上、右上、左下、右下即可，其余操作大体一致。

解题方法

1.定义并初始化给定矩阵的行，列（rows， cols），int类型变量count（记录连通水域的个数）定义用于存储数据的List集合result。遍历二维数组land若当前位置元素为0则调用编写的DFS函数，退出DFS后将当前连通位置的水域个数添加到result中,最后将将集合中元素拷贝到一个数组中排序并返回。
2. dfs函数实现

2.1 每次将当count加一，land当前位置置为1（标记当前位置是已经遍历过的合法位置）
2.2 二维数组记录八个方位int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
2.3 for循环开始查找遍历（循环范围1-8），每次得到一个新的坐标（int newI = sr + directions[i][0];int newJ = sc + directions[i][1];）
2.4 条件判断新得到的横纵坐标不超过给定二维数组的索引范围，同时新的到的横纵坐标所在位置的值等于0则继续DFS

复杂度

时间复杂度:

$O(mn)$

空间复杂度:

$O(mn)$

Code

class Solution {
    //Recode the count of waters
    private int count = 0;
    //Recode the rows and columns of matrix
    private int rows;
    private int cols;

    /**
     * Get all Connected waters
     *
     * @param land Given matrix
     * @return int[]
     */
    public int[] pondSizes(int[][] land) {
        rows = land.length;
        cols = land[0].length;
        //Result list
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (land[i][j] == 0) {
                    count = 0;
                    dfs(i, j, land);
                    result.add(count);
                }
            }
        }
        //Sort
        int[] finalResult = new int[result.size()];
        for (int i = 0; i < finalResult.length; ++i) {
            finalResult[i] = result.get(i);
        }
        Arrays.sort(finalResult);
        return finalResult;
    }

    /**
     * Access all connected waters by DFS
     *
     * @param row  Abscissa
     * @param col  Ordinate
     * @param land Given matrix
     */
    private void dfs(int row, int col, int[][] land) {
        count++;
        //Change the current position to 1
        //which shows that it has be visited
        land[row][col] = 1;
        //Record eight bearings
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
        for (int i = 0; i < 8; ++i) {
            int newI = row + directions[i][0];
            int newJ = col + directions[i][1];

            if (newI >= 0 && newI < rows && newJ >= 0 && newJ < cols
                    && land[newI][newJ] == 0) {
                dfs(newI, newJ, land);
            }
        }
    }
}