200. 岛屿数量
题目
这种矩阵题现在第一反应就是用广度优先搜索做，类似之前算和0之间的距离那题。遍历矩阵，遇到 1 就将 1 改成 0，然后广度优先搜索找出 1 相邻的所有 1，这就是一个岛屿，以此类推。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| import collections
class Solution:
def numIslands(self, grid) -> int:
rows = len(grid)
if not rows:
return 0
cols = len(grid[0])
islands = 0
for r in range(rows):
for l in range(cols):
if grid[r][l] == '1':
islands += 1
grid[r][l] = '0'
neighbors = collections.deque([(r, l)])
while neighbors:
x, y = neighbors.popleft()
for x_, y_ in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
if 0<=x_<rows and 0<=y_<cols and grid[x_][y_] == '1':
neighbors.append([x_, y_])
grid[x_][y_] = '0'
return islands
|
