200. 岛屿数量（JS实现）

短命女 2022-11-25 11:42 92阅读 0赞

## 1 题目 ##

> 给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。  
> 岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。  
> 此外，你可以假设该网格的四条边均被水包围。  
> 示例 1:  
> 输入:  
> \[  
> \[‘1’,‘1’,‘1’,‘1’,‘0’\],  
> \[‘1’,‘1’,‘0’,‘1’,‘0’\],  
> \[‘1’,‘1’,‘0’,‘0’,‘0’\],  
> \[‘0’,‘0’,‘0’,‘0’,‘0’\]  
> \]  
> 输出: 1  
> 示例 2:  
> 输入:  
> \[  
> \[‘1’,‘1’,‘0’,‘0’,‘0’\],  
> \[‘1’,‘1’,‘0’,‘0’,‘0’\],  
> \[‘0’,‘0’,‘1’,‘0’,‘0’\],  
> \[‘0’,‘0’,‘0’,‘1’,‘1’\]  
> \]  
> 输出: 3  
> 解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

链接：https://leetcode-cn.com/problems/number-of-islands

## 2 思路 ##

**这道题思路就是图的广度优先遍历，将搜索到的1变为\#，然后统计次数就可以了**

## 3代码 ##

/** * @param {character[][]} grid * @return {number} */
    var numIslands = function(grid) { 
        let res = 0;
        let rows = grid.length;
        if (rows === 0) return 0;
        let cols = grid[0].length;
    
        for (let i=0; i<rows; i++) { 
            for (let j=0; j<cols; j++) { 
                if (grid[i][j] === '1') { 
                    res++;
                    search(i,j);
                }
            }
        }
    
        function search(i, j) { 
            if (i < 0 || j < 0 || i >= rows || j >= cols || grid[i][j] === '0' || grid[i][j] === '#') return;
    
            grid[i][j] = '#';
    
            search(i+1, j);
            search(i-1, j);
            search(i, j+1);
            search(i, j-1);
        }
    
        return res;
    };