题解 | #岛屿数量#

题目链接

岛屿数量

题目描述

时间限制：1秒 空间限制：256M

描述

给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。 岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。

例如：

输入

[ [1,1,0,0,0], [0,1,0,1,1], [0,0,0,1,1], [0,0,0,0,0], [0,0,1,1,1] ]

对应的输出为

3

示例1

输入：

[[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]

返回值：

3

示例2

输入：

[[0]]

返回值：

0

示例3

输入：

[[1,1],[1,1]]

返回值：

1

备注：

01矩阵范围<=200*200

解题思路

很典型的染色法，对每个点进行dfs，将与之相邻的为1的点全染色，用sum记录当前染色值。

简而言之，第一个岛全染色为-1，第二个岛全染色为-2，最后取最大负数的反，即为正确答案。

用一个dfs就可以解决问题。

解题代码

/**
 * 判断岛屿数量
 * @param grid string字符串型二维数组 
 * @return int整型
 */
function solve(grid) {
    // write code here
    // grid = [[1, 1, 0, 0, 0], [0, 1, 0, 1, 1], [0, 0, 0, 1, 1], [0, 0, 0, 0, 0], [0, 0, 1, 1, 1]];
    let col = grid.length;
    let row = grid[0].length;
    let sum = 0;
    let dfs = (x, y) => {
        if (grid[x][y] == 1) {
            grid[x][y] = sum;
        }
        let tox = x + 1;
        let toy = y;
        if (tox >= 0 && tox < col && toy >= 0 && toy < row && grid[tox][toy] == 1) {
            dfs(tox, toy);
        }
        tox = x - 1;
        toy = y;
        if (tox >= 0 && tox < col && toy >= 0 && toy < row && grid[tox][toy] == 1) {
            dfs(tox, toy);
        }
        tox = x;
        toy = y + 1;
        if (tox >= 0 && tox < col && toy >= 0 && toy < row && grid[tox][toy] == 1) {
            dfs(tox, toy);
        }
        tox = x;
        toy = y - 1;
        if (tox >= 0 && tox < col && toy >= 0 && toy < row && grid[tox][toy] == 1) {
            dfs(tox, toy);
        }
        return;
    }
    for (let i = 0; i < col; i++) {
        for (let j = 0; j < row; j++) {
            if (grid[i][j] == 1) {
                sum--;
                dfs(i, j);
            }
        }
    }
    sum = sum < 0 ? -sum : sum;
    return sum;
}