200. Number of Islands

Leetcode link

题目简介

/**
 * @param {character[][]} grid
 * @return {number}
 */

题目给我们一个二位数组 grid，其中元素如果为 1 表示该元素为陆地；为 0 则表示该元素为海洋

题目要求我们计算 grid 中包含有多少岛屿

岛屿的定义：上下左右四个方位都是海洋的陆地的集合

解题思路

我们需要一个二位数组 visited 来保存我们访问过的陆地

此外，当我们遍历一块陆地的时候，我们使用广度优先搜索 bfs 来遍历所有同一个岛屿的陆地，期间要更新 visited

我们通过遍历所有 grid 的元素，来判断是否有我们未访问过的陆地，如果有则岛屿数量+1

Javascript

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
    const width = grid[0].length
    const height = grid.length
    const visited = Array.from({ length: height }, _ => new Array(width).fill(false))
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    let res = 0

    const bfs = (row, col) => {
        visited[row][col] = true
        const queue = [[row, col]]
        while(queue.length > 0) {
            const location = queue.shift()

            for(const dir of dirs) {
                const newRow = location[0] + dir[0]
                const newCol = location[1] + dir[1]
                if(newRow>=0 && newRow < height && 
                newCol >=0 && newCol < width && 
                grid[newRow][newCol] === '1' && 
                !visited[newRow][newCol]) {
                    queue.push([newRow, newCol])
                    visited[newRow][newCol] = true
                }
            }
        }
    }

    for (let i = 0; i < height; i++) {
        for (let j = 0; j < width; j++) {
            if(grid[i][j] === '1' && !visited[i][j]) {
                res++
                bfs(i, j)
            }
        }
    }

    return res
};