題目描述
可用解法
DFS 深度優(yōu)先遍歷
BFS 廣度優(yōu)先遍歷
算法思路：下列代碼用BFS，循環(huán)遍歷輸入的二維列表如果遇到島嶼（即為1）溜宽，將其作為根節(jié)點(diǎn)作BFS汛蝙，注意BFS要記錄下訪問(wèn)過(guò)的結(jié)點(diǎn)，如果訪問(wèn)過(guò)則不再加入樹中
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
self.grid = grid
num = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
# BFS
if grid[i][j] == "1":
quene = list()
num += 1
quene.append([i, j])
grid[i][j] = "1"
while len(quene) != 0:
x, y = quene[0]
del quene[0]
# up
if self.Ingrid(x - 1, y) and grid[x-1][y] == "1":
grid[x - 1][y] = "0"
quene.append([x - 1, y])
# down
if self.Ingrid(x + 1, y) and grid[x+1][y] == "1":
grid[x + 1][y] = "0"
quene.append([x + 1, y])
# left
if self.Ingrid(x, y - 1) and grid[x][y-1] == "1":
grid[x][y - 1] = "0"
quene.append([x, y - 1])
# right
if self.Ingrid(x, y + 1) and grid[x][y+1] == "1":
grid[x][y + 1] = "0"
quene.append([x, y + 1])
return num
def Ingrid(self, i, j):
if i >= 0 and i < len(self.grid) and j >= 0 and j < len(self.grid[0]):
return True
else:
return False
# s = Solution().numIslands([["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]])
# print(s)
