Time: 2019-08-11
題目描述
給定一個(gè)由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格，計(jì)算島嶼的數(shù)量抒寂。一個(gè)島被水包圍，并且它是通過(guò)水平方向或垂直方向上相鄰的陸地連接而成的嚣伐。你可以假設(shè)網(wǎng)格的四個(gè)邊均被水包圍哭廉。
示例 1:
輸入:
11110
11010
11000
00000
輸出: 1
示例 2:
輸入:
11000
11000
00100
00011
輸出: 3
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/number-of-islands
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)距贷，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處柄冲。
思路
DFS遍歷，主循環(huán)是兩重for循環(huán)忠蝗，遇到元素為'1'的现横，就DFS，在DFS的過(guò)程中，將相連的元素置為'0'戒祠。
代碼
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if grid == None or len(grid) == 0:
return 0
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1': # 從是1的元素開(kāi)始遍歷
self.dfs(grid, i, j)
count += 1
return count
def dfs(self, grid, i, j):
row = len(grid)
col = len(grid[0])
# 遞歸出口
if i < 0 or i >= row or j < 0 or j >= col or grid[i][j] == '0':
return
grid[i][j] = '0' # 將'1'變成0
self.dfs(grid, i - 1, j)
self.dfs(grid, i + 1, j)
self.dfs(grid, i, j - 1)
self.dfs(grid, i, j + 1)
參考
END.
