编程题目之岛屿数量问题
今天给大家介绍一道编程题目——求解岛屿数量，这种类型的题目在大多数算法工程师笔试中经常遇到。题目来源力扣。
题目描述：
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
下面我用两种方式来解决该问题。
第一种方式：BFS(广度优先遍历)
解题思路：使用队列对每个区域中每个陆地相邻的所有陆地进行存储。
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
queue = []
nums_islands = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
nums_islands += 1
queue.append((i,j))
while len(queue) != 0:
h,w = queue.pop(0)
if h >= 0 and h =0 and w < len(grid[0]) and grid[h][w]=='1':
grid[h][w] = '0'
queue += [(h-1,w),(h+1,w),(h,w-1),(h,w+1)]
return nums_islands
第二种方式：DFS(深度优先遍历)
解题思路：使用栈对每个区域中陆地按照深度进行存储。
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
grid_h = len(grid)
if grid_h <= 0:
return 0
grid_w = len(grid[0])
if grid_w = 0 and visited[h-1][w] == 0 and grid[h-1][w] == '1':
stack.append((h-1,w))
visited[h-1][w] = 1
elif h+1 < len(grid) and visited[h+1][w] == 0 and grid[h+1][w] == '1':
stack.append((h+1,w))
visited[h+1][w] = 1
elif w+1 =0 and visited[h][w-1] == 0 and grid[h][w-1] == '1':
stack.append((h,w-1))
visited[h][w-1] = 1
else:
stack.pop()
return numIslands
作者：xuchuanqiqi
