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

---

思路

深度優(yōu)先遍歷

從頂點(diǎn)開始，到其相鄰的一個(gè)節(jié)點(diǎn)，再由此節(jié)點(diǎn)至其相鄰的節(jié)點(diǎn)，依次遍歷所有相鄰的節(jié)點(diǎn)，直到某個(gè)節(jié)點(diǎn)相鄰節(jié)點(diǎn)全部遍歷完成。

注意：

遍歷順序可自定，但所有節(jié)點(diǎn)需遵從統(tǒng)一規(guī)則

深度遍歷可能會(huì)有遺漏節(jié)點(diǎn)，因此需回溯，即全程為一個(gè)遞歸過程

解題

情況1： 網(wǎng)格不存在

返回：0

情況2： 網(wǎng)格為空（即二維數(shù)組為空數(shù)組）

返回：0

情況3： 網(wǎng)格存在且不為空

從[0,0]點(diǎn)循環(huán)列表，依次將每個(gè)點(diǎn)作為深度優(yōu)先遍歷的根節(jié)點(diǎn)

若根節(jié)點(diǎn)值為0，執(zhí)行下一輪循環(huán)

若根節(jié)點(diǎn)值為1，島數(shù)量+1，開始DFS

DFS制定規(guī)則為左右上下

遍歷過的節(jié)點(diǎn)值修改為0

題目中直接修改會(huì)對原始網(wǎng)格產(chǎn)生影響，所以深拷貝一個(gè)副本，不影響原始網(wǎng)格

---

代碼

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)

說明

用了深拷貝是因?yàn)橹苯觼G進(jìn)去原矩陣會(huì)導(dǎo)致原矩陣被修改，如果只是做題的話可以不考慮這點(diǎn)，速度和空間都會(huì)有所提升。

轉(zhuǎn)載于:https://www.cnblogs.com/tajangbay-zkr-NLP/p/10879032.html

總結(jié)

以上是生活随笔為你收集整理的【算法python实现】 -- 岛屿的个数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。