本题使用了dfs来进行岛屿数的计算。
首先介绍dfs,当地图上的一个格子是陆地的时候,那么我们会很自然地想知道他周围的格子是否也是陆地。所以当发现矩阵中某个元素为‘1’时(其index 为 r, c),我们首先将其置为 0, 意思为我们已经踏足了该陆地格子,之后从它出发的 四个方向[(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)] 各走一个格子我们来判断是否为陆地,当然还要注意四个格子不能越界, 只要是的话我们就将其变成 0, 然后继续从这个格子出发,往它的四个周围格子检查,依次递归往复,这样我们就踏足了某个岛屿上面的所有陆地格子,并且消去了整个小岛。
在遍历整个地图(矩阵)的过程中,我们可以通过上述方法,来完成对岛屿数量计数的任务。
class Solution:
def solve(self , grid: List[List[str]]) -> int:
# write code here
def dfs(grid, r, c):
grid[r][c] = 0
nr = len(grid) - 1
nc = len(grid[0]) - 1
for i, j in [(r - 1, c), (r + 1, c), (r, c + 1), (r, c - 1)]:
if 0 <= i <= nr and 0 <= j <= nc and grid[i][j] == '1':
dfs(grid, i, j)
if len(grid) == 0:
return 0
row = len(grid)
col = len(grid[0])
num_island = 0
for i in range(row):
for j in range(col):
if grid[i][j] == '1':
num_island += 1
dfs(grid, i, j)
return num_island