题目描述
可用解法
DFS 深度优先遍历
BFS 广度优先遍历
算法思路：下列代码用BFS，循环遍历输入的二维列表如果遇到岛屿（即为1），将其作为根节点作BFS，注意BFS要记录下访问过的结点，如果访问过则不再加入树中
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)
