题解 | #岛屿数量#

比较有意思的递归，主要的思路是“扩散”，“占领”。

1、面对一个二维数组，我们需要双重for循环遍历。

2、当我们遍历到当前的元素是一个'1' 那么也就是代表了一块陆地的意思。

3、我们标记当前的位置为一个另外的值，也就是 ‘2’,标识我们占领了，

4、怎么‘扩散’，我们需要从当前点发散，对当前位置的上下左右四个方向，扩散出去。

5、当扩散的时候，就又像是从一个点出发，判断当前点是否是陆地，如果是陆地就标记。

6、这样一层套一层的递归调用，当发散出去的都结束的时候，就是递归触发点结束的时候。

7、那么递归的开始点就已经把它所在的岛屿中的所有地点都标记上了‘2’，然后当这个方法结束的时候，也就是岛屿+1.

8、当我们回到for循环的视角的时候，再次判断下一个元素的值，我们发现它是‘2’，就不会再来计数了。只会计数未涉足过的地点。

9、如此便轻松计算出，当前二维数组中相连块的数量。

import java.util.*;


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

    int num = 0;
    public int solve (char[][] grid) {
        for (int i = 0; i < grid.length ; i++){
            for(int j = 0; j < grid[i].length; j++){
                // 横向
                if(grid[i][j] == '1'){
                    // 匹配到是 '1' 就开始递归扩散占领
                    dfsLand(grid,i,j);
                    // 递归停止，也就是岛屿占领完整
                    num++;
                }
            }
        }
        return num;
    }


    // 递归
    public void dfsLand(char[][] grid,int i,int j){
        // 什么时候结束
        if(i < 0 || i == grid.length || j < 0 || j == grid[i].length || grid[i][j] != '1') {
            return;
        }
        // 扫描到的是岛屿的地方就变成 '2' ,在双重for循环中遍历就不会重复计数了
        // 就算递归被重复扫描也只是被重复赋值 '2' 而已。
        grid[i][j] = '2';
        // 上
        dfsLand(grid,i-1,j);
        // 下
        dfsLand(grid,i,j+1);
        // 左
        dfsLand(grid,i+1,j);
        // 右
        dfsLand(grid,i,j-1);
    }
}