这道题可以用暴力解法:
直接全部按照顺序遍历,然后打上标记,然后遍历的时候根据标记来计算是否是同一个岛屿,然后再更改标记.
这个解法逻辑太复杂, 不推荐.
可以想想成一个雷达在扫描这张地图,然后雷达扫描的线经过的地方可以根据之前的'记录'来看是否是岛屿.
这里最简单的是用 BFS, 搜过的点都标记为 0 或者visited, 然后
BFS
的时候只搜同一个岛屿,而且把同一个岛屿击沉.这样的话只需要两个
for 循环, 一个递归就可以解决. 代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
count = 0
def dfs(grid, row, column):
grid[row][column] = '0'
if row - 1 >= 0 and grid[row-1][column] == '1':
dfs(grid, row-1, column)
if column - 1 >= 0 and grid[row][column-1] == '1':
dfs(grid, row, column-1)
if row + 1 < len(grid) and grid[row+1][column] == '1':
dfs(grid, row+1, column)
if column + 1 < len(grid[0]) and grid[row][column+1] == '1':
dfs(grid, row, column+1)
for i, row in enumerate(grid):
for j, num in enumerate(row):
if num == '1':
count += 1
dfs(grid, i, j)
return count
|