200. 岛屿数量

[Geekhyt]

原题链接

深度优先遍历

先明确，题意要求我们找到矩阵中的岛屿数量，上下左右相连接的 '1' 是连续的 1 座岛屿。

1. 从起点 (i, j) 的上下左右四个方向进行深度搜索。
2. 搜索过程中，将搜索过的岛屿标记为 '0'。
3. 遍历整个矩阵，当 grid[i][j] === '1' 时，进行搜索并且将岛屿数加 1。
4. 注意递归终止条件

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)

[guoqiufeng-tal]

666