695. Max Area of Island

Question: Max Area of Island 

Solution1 BFS

想法：

這題可以先參考 200. Number of Islands 這題，解法幾乎一模一樣，只差在 return 值，200 題是 return 有幾個 island，這邊要 return 最大面積。

for loop 從 grid[0][0] 開始看，只要遇到 1 的而且沒有找過，就進入 BFS

return 的值會是 area，取大的記下來

BFS

• 準備一個 queue，需要找的座標放進去 (r, c)
• 準備一個 set visited，把找過的點座標放進去，避免重複
• 當 queue 裡有做標時，就拿出來檢查：
• 把 (r, c) 加入 visited
• 確認 grid[r][c] == 1 後 area += 1
  • 座標是否合法：r < rows 的長度; c < columns 的長度; r > -1; c > -1
  • 座標是否在 visited 裡
  • 把上下左右的可能加入 queue
  • 把上下左右的可能加入 visited
• return area

from collections import deque

class Solution:

def maxAreaOfIsland(self, grid: list[list[int]]) -> int:

rows, columns = len(grid), len(grid[0])

visited = set()

area = 0

def bfs(r, c, area):

q = deque([(r, c)])

while q:

r, c = q.popleft()

visited.add((r, c))

if grid[r][c] == 1:

area += 1

if (r + 1, c) not in visited and r + 1 < len(grid):

q.append((r + 1, c))

visited.add((r + 1, c))

if (r - 1, c) not in visited and r - 1 > -1:

q.append((r - 1, c))

visited.add((r - 1, c))

if (r, c + 1) not in visited and c + 1 < len(grid[0]):

q.append((r, c + 1))

visited.add((r, c + 1))

if (r, c - 1) not in visited and c - 1 > -1:

q.append((r, c - 1))

visited.add((r, c - 1))

return area

for r in range(rows):

for c in range(columns):

if (r, c) not in visited and grid[r][c] == 1:

area = max(area, bfs(r, c, 0))

return area

Solution2 DFS

想法：

for loop 每一格，只要 grid[r][c] == 1 且沒有被找過，就 return 那一個 island 的面積。
需要一個 function，input 座標，return area

遞迴

終止條件

• (r, c) 不在範圍內: r < 0; c < 0, r > rows - 1; c > columns - 1;
• (r, c) 已經拜訪過: (r, c) in path
• (r, c) == 0
• return 0

遞迴條件

此時 (r, c) 的 island 面積，會是「前後左右」相加，每一個 grid[r][c] 的面積都會是他的前後左右相加，因此 area 的算法就會是：自己 1 + 前 + 後 + 左 + 右 的面積總合。

class Solution:

def maxAreaOfIsland(self, grid: list[list[int]]) -> int:

rows, columns = len(grid), len(grid[0])

visited = set()

area = 0

def dfs(r, c):

if (r > rows - 1 or

c > columns - 1 or

r < 0 or

c < 0 or

(r, c) in visited or

grid[r][c] == 0):

return 0

visited.add((r, c))

return (1 + dfs(r + 1, c) +

dfs(r - 1, c) +

dfs(r, c + 1) +

dfs(r, c - 1))

for r in range(rows):

for c in range(columns):

area = max(area, dfs(r, c))

return area

Video Solution