Open
Description
深度优先遍历
先明确，题意要求我们找到矩阵中的岛屿数量，上下左右相连接的 '1' 是连续的 1 座岛屿。
- 从起点 (i, j) 的上下左右四个方向进行深度搜索。
- 搜索过程中，将搜索过的岛屿标记为 '0'。
- 遍历整个矩阵，当
grid[i][j] === '1'时，进行搜索并且将岛屿数加 1。 - 注意递归终止条件
const numIslands = function(grid) {
const dfs = function(grid, i, j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === '0') {
return
}
grid[i][j] = '0'
dfs(grid, i + 1, j)
dfs(grid, i, j + 1)
dfs(grid, i - 1, j)
dfs(grid, i, j - 1)
}
let count = 0
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === '1') {
dfs(grid, i, j)
count++
}
}
}
return count
}- 时间复杂度：O(m * n)
- 空间复杂度：O(m * n)