课堂小结:dfs 可用于搜索连通块大小,暴力枚举所有情况等。dfs 在网格中的写法:
1dir = [(0, 1), (1, 0), (-1, 0), (0, -1)]2def dfs(x, y):3 global area4 area += 15 vis[x][y] = True6 for dx, dy in dir:7 tx, ty = x+dx, y+dy8 if 0 <= tx <= n -1 and 0 <= ty <= n-1 and a[tx][ty] == '#' and not vis[tx][ty]:9 dfs(tx, ty)
和 bfs 类似,枚举 4 个方向。搜索连通块和枚举所有情况时都要注意,判断每个状态是否已经走过,可用二维数组或者 set 判断.