https://leetcode-cn.com/problems/number-of-islands/
点击查看【bilibili】
题目
给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
示例
输入:grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出:1
输入:grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出:3
解答
沉没:如果找到1,把周边的1都变成0(沉没掉),记录小岛+1
从第一个点开始,如果是1,由1改为0,向四周扩散
判断保证不越界
依次判断周边的点是否是1
答案
// bfs-(宽)广度优先搜索
// dfs- 深度优先搜索
var numIslands = function(grid) {
let count = 0
function dfs(row,col) {
// 判断越界和为0的情况
if(row<0 || row>=grid.length || col<0 || col>=grid[0].length || grid[row][col] === '0') {
return
}
grid[row][col] = '0'
// 向四周扩散
dfs(row-1, col)
dfs(row+1, col)
dfs(row, col-1)
dfs(row, col+1)
}
for(let row=0;row<grid.length;row++) {
for(let col=0;col<grid[0].length;col++) {
if(grid[row][col] === '1') {
count++;
dfs(row,col)
}
}
}
return count
};