1.島嶼數量
99. 島嶼數量
🌟 思路總結 — DFS 版
1?? 問題本質
給定一個二維矩陣
grid，1 表示陸地，0 表示水統計島嶼數量，每個島嶼由上下左右相鄰的陸地組成
本質是 在二維網格中找連通塊 的問題。
2?? 核心思路
遍歷矩陣
對每個格子
(i,j)：
如果是陸地 (
grid[i][j] == 1) 且未訪問過
→ 說明發現一個新島嶼，島嶼計數 +1DFS 擴展島嶼
從新發現的陸地出發，深度優先遞歸訪問上下左右相鄰的陸地
每訪問一個陸地就標記為已訪問
visited[i][j] = True遞歸結束后，這塊島嶼的所有陸地都被標記，避免重復計數
返回島嶼數量
遍歷完矩陣后，島嶼計數就是答案
3?? 核心技巧
方向數組：
direction = [[0,1],[1,0],[0,-1],[-1,0]] # 右、下、左、上
遍歷鄰居時統一處理
next_x = x + dx,next_y = y + dy
訪問標記：
用
visited二維布爾數組標記已訪問的陸地DFS 或 BFS 入隊/遞歸時立即標記，防止重復訪問
越界判斷：
if nextx < 0 or nextx >= n or nexty < 0 or nexty >= m: continue
避免訪問矩陣外的元素
#深度優先
direction = [[0, 1], [1, 0], [-1, 0], [0, -1]] #依次是右，下， 上， 左
def dfs(grid, visited, x, y):for i, j in direction:nextx = x + inexty = y + j#判斷是否越界if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):continue# 如果是陸地且未訪問if grid[nextx][nexty] == 1 and visited[nextx][nexty] == False:visited[nextx][nexty] = Truedfs(grid, visited, nextx, nexty)def main():#輸入，存圖n, m = map(int, input().split())grid = []for i in range(n):grid.append(list(map(int, input().split())))visited = [[False] * m for _ in range(n)]result = 0for i in range(n):for j in range(m):if grid[i][j] == 1 and visited[i][j] == False:result += 1visited[i][j] = True#dfsdfs(grid, visited, i, j)return resultif __name__ == "__main__":print(main())2.廣度優先搜索的理論基礎
步驟:先將起點加入隊列， 標記為true， 取出當前節點，沿四個方向遍歷判斷是否訪問過，未訪問則加入隊列，標記為true。直至隊列為空則廣搜結束
direction = [[0,1], [1, 0], [-1, 0], [0, -1]]def bfs(grid, visited, x, y):que = deque()que.apppend(x, y)visited[x][y] == Truewhile que:curx, cury = que.popleft()for i, j in direction:nextx = curx + inexty = cury + jif nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):continueif not visited[nextx][nexty]:que.append([nextx, nexty])visited[nextx][nexty] == 1
島嶼數量用廣度搜索重做一遍：
from collections import dequedirection = [[0, 1], [1, 0], [-1, 0], [0, -1]] def bfs(grid, visited, x, y):queue = deque()queue.append([x, y])visited[x][y] = Truewhile queue:cur_x, cur_y = queue.popleft() #取出隊首元素for i, j in direction:nextx = cur_x + inexty = cur_y + jif nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):continueif not visited[nextx][nexty] and grid[nextx][nexty] == 1:visited[nextx][nexty] = Truequeue.append([nextx, nexty])def main():n, m = map(int, input().split())grid = []for i in range(n):grid.append(list(map(int, input().split())))visited = [[False] * m for _ in range(n)]result = 0for i in range(n):for j in range(m):if grid[i][j] == 1 and not visited[i][j]:result += 1bfs(grid, visited, i, j)print(result)if __name__ == "__main__":main()
3.島嶼的最大面積
📝 代碼功能
這是一個求最大島嶼面積的程序（不是島嶼數量）。
輸入一個
n×m的矩陣grid，1表示陸地，0表示水。使用 DFS（深度優先搜索）遍歷每一塊島嶼，同時統計它的面積。
最終輸出所有島嶼中的最大面積。
🔑 核心思路
方向數組
direction = [[0, 1], [1, 0], [-1, 0], [0, -1]]用來表示四個相鄰方向：右、下、上、左。
DFS 深度優先搜索
def dfs(grid, visited, x, y): global area for i, j in direction: nextx = x + i nexty = y + j ...
從一個陸地
(x, y)出發，遞歸探索它相鄰的陸地；每發現一個新的陸地，就
area += 1；并且標記
visited[nextx][nexty] = True，避免重復訪問。遍歷矩陣
for i in range(n): for j in range(m): if grid[i][j] == 1 and not visited[i][j]: area = 1 visited[i][j] = True dfs(grid, visited, i, j) res = max(res, area)
遍歷整個矩陣；
每遇到一個未訪問的陸地
(i, j)，說明發現一塊新島嶼；從這里開始 DFS，計算該島嶼面積；
更新最大面積
res。
direction = [[0, 1], [1, 0], [-1, 0], [0, -1]]
area = 0
def dfs(grid, visited, x, y):global areafor i, j in direction:nextx = x + inexty = y + jif nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):continueif not visited[nextx][nexty] and grid[nextx][nexty] == 1:area += 1visited[nextx][nexty] = Truedfs(grid, visited, nextx, nexty)n, m = map(int, input().split())
grid = []
for i in range(n):grid.append(list(map(int, input().split())))
visited = [[False] * m for _ in range(n)]
res = 0for i in range(n):for j in range(m):if grid[i][j] == 1 and not visited[i][j]:area = 1visited[i][j] = Truedfs(grid, visited, i, j)res = max(res, area)
print(res)今日結束啦！！！
