JZX轻语：简
LeetCode 695 - 岛屿的最大面积
发表于2024年04月15日
DFS往四个方面扩展面积即可，使用一个visited数组来维护已经访问的信息，如果遍历到已经visit的节点则不再统计。
class Solution:
moves = [
(-1, 0),
(0, -1),
(1, 0),
(0, 1)
]
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
visited = [[False] * n for _ in range(m)]
def dfs(x: int, y: int) -> int:
nonlocal visited
if grid[y][x] == 0:
return 0
result = 1
for move in self.moves:
nx = x + move[0]
ny = y + move[1]
if 0 <= nx < n and 0 <= ny < m and not visited[ny][nx]:
visited[ny][nx] = True
result += dfs(nx, ny)
return result
r = 0
for i in range(m):
for j in range(n):
if grid[i][j] and not visited[i][j]:
visited[i][j] = True
r = max(r, dfs(j, i))
return r