200. Number of Islands
這一題的重點在於於圖形中，進行深度優先搜索或是廣度優先搜索的遍歷。
今天的題目條件在於，如果一個陸地屬於一個島嶼的話，那該陸地一定是與其他陸地的四個方向之一有相連，要計算出有幾個島嶼，我只要站在島嶼上的任何一塊陸地，把該島嶼全部都標記成已經造訪過，那我就可以確定這個島嶼已經造訪完畢，計數器加一，接著再繼續找到下一個尚未被標記的陸地即可。
深度優先搜索
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
rows = len(grid)
cols = len(grid[0])
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def dfs(row, col):
grid[row][col] = '#'
for dr, dc in directions:
next_row = row+dr
next_col = col+dc
if 0 <= next_row < rows and 0 <= next_col < cols and grid[next_row][next_col] == '1':
dfs(next_row, next_col)
islands = 0
for row in range(rows):
for col in range(cols):
if grid[row][col] == '1':
islands += 1
dfs(row, col)
return islands 廣度優先搜索
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or not grid[0]:
return 0
rows = len(grid)
cols = len(grid[0])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
islands = 0
def bfs(i, j):
queue = deque([(i, j)])
while queue:
row, col = queue.popleft()
grid[row][col] = '#'
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] == "1":
queue.append((new_row, new_col))
grid[new_row][new_col] = '#'
for i in range(rows):
for j in range(cols):
if grid[i][j] == "1":
islands += 1
bfs(i, j)
return islands