200. Number of Islands

Question: Number of Islands

Solution

想法：

Graphs 的解法！BFS

BFS

1. 用 deque，把沒看過的 path 放進去。
2. 準備一個 set，把拜訪過的 path 放進去，避免重複看。
3. 用 while 迴圈，只要 deque 裡有東西，就 pop 出來看，檢查他，再繼續看他的鄰居，把鄰居加入 deque

class Solution:

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

visited = set()

def bfs(r, c):

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

visited.add((r, c))

while q:

r, c = q.popleft()

if grid[r][c] == "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

island = 0

for r in range(len(grid)):

for c in range(len(grid[0])):

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

bfs(r, c)

island += 1

return island

Solution2

這裡也提供 DFS 的解法，但相對比較久

from collections import deque

class Solution:

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

island = set()

def dfs(r, c):

if (r < 0 or

c < 0 or

r > len(grid) - 1 or

c > len(grid[0]) - 1 or

grid[r][c] == "0" or

(r, c) in island):

island.add((r, c))

return

else:

island.add((r, c))

dfs(r + 1, c)

dfs(r - 1, c)

dfs(r, c + 1)

dfs(r, c - 1)

res = 0

for r in range(len(grid)):

for c in range(len(grid[0])):

if grid[r][c] == "0" or (r, c) in island:

continue

else:

dfs(r, c)

res += 1

return res

Video Solution