题解 | #岛屿数量#

深度优先搜索(DFS)

• 深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。
• 它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。

如何不重复统计岛屿？

为了不重复统计岛屿，可以在遇到1时把相邻的上下左右4个方向都置为0，这个过程是深度优先搜索的，即如果相邻的上下左右四个方向的内容是1，则将其置为0的过程中继续对这个位置的相邻上下左右四个方向的内容置为0

• 终止条件： 进入某个元素修改其值为0后，遍历四个方向发现周围都没有1，那就不用继续递归，返回即可，或者递归到矩阵边界也同样可以结束。
• 返回值： 每一级的子问题就是把修改后的矩阵返回，因为其是函数引用，也不用管。
• 本级任务： 对于每一级任务就是将该位置的元素置为0，然后查询与之相邻的四个方向，看看能不能进入子问题。

参考

https://blog.nowcoder.net/n/f6365fcd7f89430fa6eda6f7ce525dea?f=comment

/*
 * @Author: LibraStalker **********
 * @Date: 2023-04-20 11:41:32
 * @FilePath: BM57-岛屿数量.js
 * @Description: 
 */
/**
 * 判断岛屿数量
 * @param grid string字符串型二维数组 
 * @return int整型
 */
function solve( grid ) {
    let n = grid.length;
    if (n === 0) return 0;
    let m = grid[0].length;

    let count = 0;
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < m; ++j) {
            if (grid[i][j] === "1") {
                count += 1;
                dfs(grid, i, j);
            }
        }
    }

    return count;
    // write code here
    function dfs(grid, i, j) {
        const n = grid.length;
        const m = grid[0].length;

        grid[i][j] = 0;  // 遇到1则将相邻的1全部变成0，这样就不会重复统计岛屿了

        if (i-1 >= 0 && grid[i-1][j] === "1") {  // 上面的1
            dfs(grid, i-1, j);
        }
        if (i+1 < n && grid[i+1][j] === "1") {  // 下面的1
            dfs(grid, i+1, j);
        }
        if (j-1 >= 0 && grid[i][j-1] === "1") {  // 左面的1
            dfs(grid, i, j-1);
        }
        if (j+1 < m && grid[i][j+1] === "1") {  // 右面的1
            dfs(grid, i, j+1);
        }
    }
}
module.exports = {
    solve : solve
};