[tag] BFS
- samilar to number of islands
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
max_area = 0
len1 = len(grid)
len2 = len(grid[0])
print(len1, len2)
grid_queue = deque()
for i in range(len1):
for j in range(len2):
if grid[i][j]:
grid_queue.append([i,j])
grid[i][j] = 0
cur_area = 0
while grid_queue:
x, y = grid_queue.popleft()
cur_area += 1
if cur_area > max_area:
max_area = cur_area
for one_dir in dirs:
new_x = x + one_dir[0]
new_y = y + one_dir[1]
if (0 <= new_x < len1) and (0 <= new_y < len2) and (grid[new_x][new_y]):
grid_queue.append([new_x, new_y])
grid[new_x][new_y] = 0
return max_area