200. Number of Islands

[Tcdian]

200. Number of Islands

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

Example 1

Input:
11110
11010
11000
00000

Output: 1

Example 2

Input:
11000
11000
00100
00011

Output: 3

[Tcdian]

Solution 1 ( DFS )

• JavaScript Solution

/**
 * @param {character[][]} grid
 * @return {number}
 */
// DFS 递归
var numIslands = function(grid) {
    const mark = Array.from(new Array(grid.length), () => new Array(grid[0].length).fill(0));
    let result = 0;

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1' && mark[i][j] === 0) {
                result++;
                dfs(i, j);
            }
        }
    }

    return result;

    function dfs(i, j) {
        mark[i][j] = 1;
        const direction = [-1, 0, 1, 0, -1];

        for (let d = 0; d < 4; d++) {
            const dx = i + direction[d];
            const dy = j + direction[d + 1];
            if (
                dx >= 0
                    && dx < mark.length
                    && dy >= 0 
                    && dy < mark[0].length
                    && grid[dx][dy] === '1'
                    && mark[dx][dy] === 0
            ) {
                dfs(dx, dy);
            }
        }
    }
};

/**
 * @param {character[][]} grid
 * @return {number}
 */
// DFS 非递归
var numIslands = function(grid) {
    const mark = Array.from(new Array(grid.length), () => new Array(grid[0].length).fill(0));
    let result = 0;

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1' && mark[i][j] === 0) {
                result++;
                dfs(i, j);
            }
        }
    }

    return result;

    function dfs(i, j) {
        mark[i][j] = 1;
        const direction = [-1, 0, 1, 0, -1];
        const stack = [[i, j]];

        while (stack.length !== 0) {
            const [x, y] = stack.pop();
            for (let d = 0; d < 4; d++) {
                const dx = x + direction[d];
                const dy = y + direction[d + 1];
                if (
                    dx >= 0
                        && dx < mark.length
                        && dy >= 0 
                        && dy < mark[0].length
                        && grid[dx][dy] === '1'
                        && mark[dx][dy] === 0
                ) {
                    mark[dx][dy] = 1;
                    stack.push([dx, dy]);
                }
            }
        }  
    }
};

Solution 2 ( BFS )

• JavaScript Solution

/**
 * @param {character[][]} grid
 * @return {number}
 */
// BFS
var numIslands = function(grid) {
    const mark = Array.from(new Array(grid.length), () => new Array(grid[0].length).fill(0));
    let result = 0;

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1' && mark[i][j] === 0) {
                result++;
                bfs(i, j);
            }
        }
    }

    return result;

    function bfs(i, j) {
        mark[i][j] = 1;
        const direction = [-1, 0, 1, 0, -1];
        const queue = [[i, j]];

        while (queue.length !== 0) {
            const [x, y] = queue.shift();
            for (let d = 0; d < 4; d++) {
                const dx = x + direction[d];
                const dy = y + direction[d + 1];
                if (
                    dx >= 0
                        && dx < mark.length
                        && dy >= 0 
                        && dy < mark[0].length
                        && grid[dx][dy] === '1'
                        && mark[dx][dy] === 0
                ) {
                    mark[dx][dy] = 1;
                    queue.push([dx, dy]);
                }
            }
        }  
    }
};