# **Leetcode筆記(Pacific Atlantic Water Flow)** :::info :information_source: 題目 : Pacific Atlantic Water Flow, 類型 : graph , 等級 : medium 日期 : 2023/04/15，2023/05/18，2023/07/13 ::: ### 嘗試 2023/05/18 ```python class Solution: def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: m, n = len(heights), len(heights[0]) pac, atl = [[False] * n for i in range(m)], [[False] * n for i in range(m)] dirs =[(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(r, c, sea, prev): if r < 0 or r >= m or c < 0 or c >= n or heights[r][c] < prev or sea[r][c]: return False sea[r][c] = True for dr, dc in dirs: nr, nc = r + dr, c + dc if dfs(nr, nc, sea, heights[r][c]): # 這裡其實可以省略 因為重點在標記sea[r][c] return True # 跳出這個迴圈 到starting去執行下一步 return False # 從邊出發(starting) for r in range(m): dfs(r, 0, pac, 0) # 左 dfs(r, n - 1, atl, 0) # 右 for c in range(n): dfs(0, c, pac, 0) # 上 dfs(m - 1, c, atl, 0) # 下 res = [] # 兩邊皆可流通 for r in range(m): for c in range(n): if pac[r][c] and atl[r][c]: res.append([r, c]) return res ``` 2023/07/13 從pac和atl的每個點去做dfs，從該點進入matrix，看能到達哪一點(代表那點和這個海洋互通) 同時也要記錄pre，這條dfs路徑的高度必須不停遞增，才可以通 ```python class Solution: def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: m, n = len(heights), len(heights[0]) dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] pac, atl = [[False] * n for _ in range(m)], [[False] * n for _ in range(m)] res = [] def dfs(r, c, sea, pre): if r < 0 or c < 0 or r >= m or c >= n or sea[r][c] or heights[r][c] < pre: return sea[r][c] = True for dr, dc in dirs: nr, nc = r + dr, c + dc dfs(nr, nc, sea, heights[r][c]) return for r in range(m): dfs(r, 0, pac, 0) dfs(r, n - 1, atl, 0) for c in range(n): dfs(0, c, pac, 0) dfs(m - 1, c, atl, 0) for r in range(m): for c in range(n): if pac[r][c] and atl[r][c]: res.append([r, c]) return res ``` --- ### **優化** 時間複雜度為 $O(mn)$，其中 $m$ 是矩陣的行數，$n$ 是矩陣的列數。每個格子最多只會被遍歷一次，因此時間複雜度為線性的。 空間複雜度為 $O(mn)$，主要是用來存儲訪問數組、太平洋和大西洋的可達情況。 ```python class Solution: def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: ROW, COL = len(heights), len(heights[0]) # [[False] * 行 for i in range(列)] pac = [[False] * COL for i in range(ROW)] atl = [[False] * COL for i in range(ROW)] def dfs(r, c, visit, pre_height): if (r < 0 or c < 0 or r == ROW or c == COL or visit[r][c] or pre_height > heights[r][c]): return visit[r][c] = True # 可以流通 # 往四個方向 dfs(r + 1, c, visit, heights[r][c]) dfs(r - 1, c, visit, heights[r][c]) dfs(r, c + 1, visit, heights[r][c]) dfs(r, c - 1, visit, heights[r][c]) # dfs(row, column, ocean, previous height) # 最左和最上出發往中間 代表為pacific # 最右和最下出發往中間 代表為atlantic # starting for r in range(ROW): dfs(r, 0, pac, heights[r][0]) dfs(r, COL - 1, atl, heights[r][COL - 1]) for c in range(COL): dfs(0, c, pac, heights[0][c]) dfs(ROW - 1, c, atl, heights[ROW - 1][c]) # 確認有誰是true res = [] for r in range(ROW): for c in range(COL): if pac[r][c] and atl[r][c]: res.append([r, c]) return res ``` --- **:warning: 錯誤語法** :::warning ::: **:thumbsup:學習** :::success graph網格，基本上都用dfs，用一個index紀錄 [[False] * 行 for i in range(列)] ::: **思路** **講解連結** https://www.youtube.com/watch?v=s-VkcjHqkGI Provided by. NeetCode ###### tags: `graph` `medium` `leetcode`