原题： https://leetcode-cn.com/problems/number-of-islands/

---

思路

深度优先遍历

从顶点开始，到其相邻的一个节点，再由此节点至其相邻的节点，依次遍历所有相邻的节点，直到某个节点相邻节点全部遍历完成。

注意：

遍历顺序可自定，但所有节点需遵从统一规则

深度遍历可能会有遗漏节点，因此需回溯，即全程为一个递归过程

解题

情况1： 网格不存在

返回：0

情况2： 网格为空（即二维数组为空数组）

返回：0

情况3： 网格存在且不为空

从[0,0]点循环列表，依次将每个点作为深度优先遍历的根节点

若根节点值为0，执行下一轮循环

若根节点值为1，岛数量+1，开始DFS

DFS制定规则为左右上下

遍历过的节点值修改为0

题目中直接修改会对原始网格产生影响，所以深拷贝一个副本，不影响原始网格

---

代码

import copyclass Solution:def numIslands(self, grid) -> int:if not grid or not grid[0]:return 0loc_grid = copy.deepcopy(grid)self.m, self.n = len(loc_grid), len(loc_grid[0])num = 0for i in range(self.m):for j in range(self.n):if int(loc_grid[i][j]) == 0:continuenum += 1self.__dfs(loc_grid, i, j)return numdef __dfs(self, loc_grid, i, j):if i < 0 or i == self.m or j < 0 or j == self.n:returnif int(loc_grid[i][j]) == 0:returnloc_grid[i][j] = 0self.__dfs(loc_grid, i, j-1)self.__dfs(loc_grid, i, j+1)self.__dfs(loc_grid, i-1, j)self.__dfs(loc_grid, i+1, j)

说明

用了深拷贝是因为直接丢进去原矩阵会导致原矩阵被修改，如果只是做题的话可以不考虑这点，速度和空间都会有所提升。

转载于:https://www.cnblogs.com/tajangbay-zkr-NLP/p/10879032.html

总结

以上是生活随笔为你收集整理的【算法python实现】 -- 岛屿的个数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。