题解 | #岛屿数量#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断岛屿数量
     * @param grid char字符型二维数组
     * @return int整型
     */
    public int solve (char[][] grid) {
        // write code here

        // 采用二维数组的深度递归尝试方法
        // 算法的时间复杂度为O(N)，额外空间复杂度为O(1)

        // 1.先统计二维数组的高和宽
        int height = grid.length;
        int weight = grid[0].length;

        // 2.遍历二维数组，每遇到一个'1'就代表踏上了一个岛，执行深度递归尝试，将该岛的所有位置全置'2'表示已经到达过了
        int count = 0;
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < weight; j++) {
                if (grid[i][j] == '1') {
                    // 找到了一座岛，数量自增，执行深度递归尝试
                    count++;
                    process(grid, i, j, height, weight);
                }
            }
        }

        // 3.返回岛屿数量
        return count;
    }

    // 深度递归尝试，将该岛的所有位置全置'2'表示已经到达过了
    public void process(char[][] grid, int i, int j, int height, int weight) {
        // 递归出口
        if (i < 0 || i >= height || j < 0 || j >= weight || grid[i][j] != '1') {
            // 若当前位置越界或不是岛，则退出
            return;
        }

        // 当前位置不越界且是岛
        // 先置'2'表示到达过了
        grid[i][j] = '2';

        // 对四个方向（上下左右）进行递归
        process(grid, i - 1, j, height, weight);
        process(grid, i + 1, j, height, weight);
        process(grid, i, j - 1, height, weight);
        process(grid, i, j + 1, height, weight);
    }
}