算法刷题Day22:BM57 岛屿数量

题目链接

描述：
给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
例如：
输入
[
[1,1,0,0,0],
[0,1,0,1,1],
[0,0,0,1,1],
[0,0,0,0,0],
[0,0,1,1,1]
]
对应的输出为3
(注：存储的01数据其实是字符’0’,‘1’)

思路

无需思路，全是套路。递归+visited数组 优雅控制四个方向。
写递归三部曲：退出条件，递归体，返回值。

代码

# 控制方向
directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def dfs(grid, visited, lenx, leny, x, y):
	# 判断坐标轴是否合法
    if x < 0 or y < 0 or x >= lenx or y >= leny:
        return
	# 访问过的节点或者是0号节点就不用管了，直接return
    if visited[x][y] or grid[x][y]=='0':
        return
    visited[x][y] = True
    # 递归四个方向
    for dx, dy in directs:
        nx = x + dx
        ny = y + dy
        dfs(grid, visited, lenx, leny, nx, ny)
        
class Solution:
    def solve(self, grid: List[List[str]]) -> int:
        # write code here
        rows = len(grid)
        cols = len(grid[0])
        # 创建visited二维数组
        visited = [[False for _ in range(cols)] for _ in range(rows)]

        tag = 0 # 记录多少个岛
        for i in range(rows):
            for j in range(cols):
            	# 如果是1，且没有访问过，就递归访问
                if grid[i][j] == "1" and not visited[i][j]:   
                    tag += 1
                    dfs(grid, visited, rows, cols, i, j)
        return tag 

这个题，原来如此优雅