BM57题解 | #岛屿数量#

dfs方法

这是一道很经典的面试题

我们要找连在一起的'1'，所以我们遍历grid中的每一个元素

如果遍历到的当前元素是'1'说明我们发现了新大陆，就让计数器count++，并将这个位置的'1'置为'0'（做一个标记）

之后我们要把连在一起的'1'给排除了，因为这些'1'被认定为和当前遍历到的这个'1'是同一座岛屿

这就需要用到深度搜索了，我们的递归主要是往4个方向进行，上右下左，找有没有连在一起的'1'，如果有，也置'0'（做标记）

这样就相当于把整座岛记录下来并且标记了，不会对后续的遍历产生影响

最后当grid遍历完了之后，res中记录的就是岛屿的数量，返回即可

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断岛屿数量
     * @param grid char字符型二维数组 
     * @return int整型
     */
    public int solve (char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int res = 0; // 定义一个结果计数器
        int row = grid.length;
        int col = grid[0].length;
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (grid[i][j] == '1') {
                    res++;
                    dfs(grid, i, j, row, col);
                }
            }
        }
        return res;
    }

    private void dfs(char[][] grid, int x, int y, int row, int col) {
        // 边界条件，超出  ->  递归终止
        if (x < 0 || y < 0 || x >= row || y >= col || grid[x][y] == '0') {
            return;
        }
        // 如果判断到是陆地，就记录计数器，并把它标记成水域
        grid[x][y] = '0';
        // 四个方向扩散递归
        dfs(grid, x-1, y, row, col); // 上
        dfs(grid, x, y+1, row, col); // 右
        dfs(grid, x+1, y, row, col); // 下
        dfs(grid, x, y-1, row, col); // 左
    }
}