# 刷題筆記 - LeetCode 417. Pacific Atlantic Water Flow
https://leetcode.com/problems/pacific-atlantic-water-flow
## Thoughts
這題是給一個 grid，grid 上方及左側連接 Pacific Ocean，下方及右側連接 Atlantic Ocean。grid 上的格子數值代表高度，水只能從高度較高或相等的格子流向高度較低或相等的格子。而與海洋相鄰的格子，水自然能夠留到海洋。
這題想要找出的是，哪些格子的水可以同時流向 Pacific Ocean & Atlantic Ocean？
首先想到的是
1. 要遍歷每個格子嗎？目的是？
2. 有些格子的水可以流到兩個海洋，但有些格子只能留到一個海洋
3. 在判斷是不是能夠流到某個海洋時，必須判斷自己這個點的高度以及流過來的方向的格子的高度
問題很多，直接看 DFS 解法
## Solution 1 - DFS, Recursion
### Logic
鄰接海洋的四個邊界的格子的水，一定能夠流到鄰近的海洋，也就是第一列及第一行的格子上的水一定可以流向 Pacific Ocean、最後一列及最後一行的格子上的水一定可以流向 Atlantic Ocean。
這題是想要找「可以流向兩個海洋」的格子，那麼可以先拆分成兩個問題：
1. 流向 Pacific Ocean
2. 流向 Atalntic Ocean
拆分成每個海洋來看，就變成是
- 第 `0` row & 第 `0` column 能流進 Pacific Ocean
- 第 `rows-1` row & 第 `cols-1` column 能流進 Atlantic Ocean
再來 DFS 是遍歷每個格子，但我們已經知道前述的四個邊界一定可以流向海洋，反過來說，如果某個未靠海的格子的水可以流到海洋，整個水流的路徑勢必包括這四個邊界的其中一格。所以我們可以反過來從這四個邊界開始走 DFS，可以走得到的地方就代表該格子的水能夠流向某個海洋。
我們分別儲存
1. 可以流向 Pacific Ocean 的位置
2. 可以流向 Atalntic Ocean 的位置
最後再取交集，就會是**可以流向兩個海洋**的格子
最後一個問題是，假設從邊界出發往內部遍歷，要怎麼判斷繼續往下走或是停止？
- 最基本的條件當然是不能超過邊界，所以不能超過 `rows`, `columns`
- 再來如果已經訪問過的格子，我們可以先儲存起來，就不需要再確認一次
- 最後，水只能流向高度小於所在高度的格子，但我們現在是反過來從靠近海洋的格子出發，因此我現在所在的格子，要可以往下走，代表**我的高度要大於等於來源格子的高度**
從這幾點可以推測出，我們寫的這個 DFS function 會需要輸入幾個資訊：
- 現在這個點的位置 (x, y)
- 是否已經訪問過，我們會建立兩個集合給兩個海洋，所以這邊需要輸入對應的海洋的集合 (Set)
- 來源格子的高度
### Code
接下來看程式碼說明
```python=
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
rows = len(heights)
cols = len(heights[0])
pac, atl = set(), set()
# check from ocean to cell -> height should be equal or increasing
def dfs(i, j, visited, prev_height):
if (i < 0 or i > rows - 1 or j < 0 or j > cols - 1
or (i, j) in visited
or heights[i][j] < prev_height):
return
visited.add((i, j))
dfs(i-1, j, visited, heights[i][j])
dfs(i+1, j, visited, heights[i][j])
dfs(i, j-1, visited, heights[i][j])
dfs(i, j+1, visited, heights[i][j])
for j in range(cols):
dfs(0, j, pac, heights[0][j])
dfs(rows-1, j, atl, heights[rows-1][j])
for i in range(rows):
dfs(i, 0, pac, heights[i][0])
dfs(i, cols-1, atl, heights[i][cols-1])
res = []
for i in range(rows):
for j in range(cols):
if (i, j) in pac and (i, j) in atl:
res.append([i, j])
return res
```
1. 首先取得整個島的 `rows` & `cols`，並建立兩個 `set()`，分別用來儲存可以走到兩個海洋的位置
2. 再來是 `dfs` function 的程式碼
如果現在檢查的這個點
- 超出邊界
- 已經存在於某個海洋的集合中
- 或是現在這個點的高度大於來源格子的高度
都表示我們不用繼續往下找，可以 return
若符合條件，代表現在這個點的水是可以流到海洋的，把它加進該海洋的集合
接下來再繼續往四個方向檢查，所以呼叫 4 個 `dfs` function
而這邊 `prev_height` 就是放上**現在這個格子**的位置(`height[i][j]`)，因為對下一個格子來說現在這個格子的位置就是來源格子
3. 完成 `dfs` function 後，開始遍歷
我們要從四個邊開始，對於第一個 row 以及最後一個 row，它們接觸的海洋分別是 Pacific Ocean & Atlantic Ocean。下面的迴圈就是固定 row 是 `0` & `rows-1`，改變 column 來遍歷
而 `prev_height` 的位置就放自己，假裝來源格子的高度跟現在的高度一樣，或是要放無限小也可以
```python
for j in range(cols):
dfs(0, j, pac, heights[0][j])
dfs(rows-1, j, atl, heights[rows-1][j])
```
再來是第一個 column 以及最後一個 column，它們接觸的海洋分別是 Pacific Ocean & Atlantic Ocean。迴圈就變成固定 column 為 `0` & `cols-1`，改變 row 來遍歷
```python
for i in range(rows):
dfs(i, 0, pac, heights[i][0])
dfs(i, cols-1, atl, heights[i][cols-1])
```
4. 走完這兩個迴圈後，可以流向單一個海洋的位置都被加進 Set 中了
就可以檢查這兩個 Set 的交集，回傳答案
#### Code with log
附上加 `print(...)` 的版本
```python=
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
rows = len(heights)
cols = len(heights[0])
pac, atl = set(), set()
def dfs(i, j, visited, prev_height, depth=0):
indent = ' ' * depth # indentation based on recursion depth
print(f"{indent}Now checking ({i}, {j})")
if i < 0 or i >= rows or j < 0 or j >= cols:
print(f"{indent}Out of bounds: ({i}, {j})")
return
if (i, j) in visited:
print(f"{indent}Already visited: ({i}, {j})")
return
if heights[i][j] < prev_height:
print(f"{indent}Cannot flow from {prev_height} to lower height {heights[i][j]} at ({i}, {j})")
return
print(f"{indent}Visiting: ({i}, {j}), height: {heights[i][j]} >= prev_height: {prev_height}")
visited.add((i, j))
dfs(i-1, j, visited, heights[i][j], depth + 1)
dfs(i+1, j, visited, heights[i][j], depth + 1)
dfs(i, j-1, visited, heights[i][j], depth + 1)
dfs(i, j+1, visited, heights[i][j], depth + 1)
print(f"\n---Check first row---")
for j in range(cols):
print(f"\nStart DFS for Pacific from (0, {j})")
dfs(0, j, pac, heights[0][j])
print(f"\n---Check last row---")
for j in range(cols):
print(f"\nStart DFS for Atlantic from ({rows-1}, {j})")
dfs(rows-1, j, atl, heights[rows-1][j])
print(f"\n---Check first column---")
for i in range(rows):
print(f"\nStart DFS for Pacific from ({i}, 0)")
dfs(i, 0, pac, heights[i][0])
print(f"\n---Check last column---")
for i in range(rows):
print(f"\nStart DFS for Atlantic from ({i}, {cols-1})")
dfs(i, cols-1, atl, heights[i][cols-1])
print("\n================================================")
print("\nPacific reachable cells:")
print(pac)
print("\nAtlantic reachable cells:")
print(atl)
res = []
print("\nResult cells that can reach both oceans:")
for i in range(rows):
for j in range(cols):
if (i, j) in pac and (i, j) in atl:
print(f" Cell ({i}, {j}) can reach both oceans")
res.append([i, j])
return res
```
Testcase
Input
```
heights =
[[1,2,5],
[3,4,4],
[2,3,1],
[6,4,5]]
```
Output
```
---Check first row---
Start DFS for Pacific from (0, 0)
Now checking (0, 0)
Visiting: (0, 0), height: 1 >= prev_height: 1
Now checking (-1, 0)
Out of bounds: (-1, 0)
Now checking (1, 0)
Visiting: (1, 0), height: 3 >= prev_height: 1
Now checking (0, 0)
Already visited: (0, 0)
Now checking (2, 0)
Cannot flow from 3 to lower height 2 at (2, 0)
Now checking (1, -1)
Out of bounds: (1, -1)
Now checking (1, 1)
Visiting: (1, 1), height: 4 >= prev_height: 3
Now checking (0, 1)
Cannot flow from 4 to lower height 2 at (0, 1)
Now checking (2, 1)
Cannot flow from 4 to lower height 3 at (2, 1)
Now checking (1, 0)
Already visited: (1, 0)
Now checking (1, 2)
Visiting: (1, 2), height: 4 >= prev_height: 4
Now checking (0, 2)
Visiting: (0, 2), height: 5 >= prev_height: 4
Now checking (-1, 2)
Out of bounds: (-1, 2)
Now checking (1, 2)
Already visited: (1, 2)
Now checking (0, 1)
Cannot flow from 5 to lower height 2 at (0, 1)
Now checking (0, 3)
Out of bounds: (0, 3)
Now checking (2, 2)
Cannot flow from 4 to lower height 1 at (2, 2)
Now checking (1, 1)
Already visited: (1, 1)
Now checking (1, 3)
Out of bounds: (1, 3)
Now checking (0, -1)
Out of bounds: (0, -1)
Now checking (0, 1)
Visiting: (0, 1), height: 2 >= prev_height: 1
Now checking (-1, 1)
Out of bounds: (-1, 1)
Now checking (1, 1)
Already visited: (1, 1)
Now checking (0, 0)
Already visited: (0, 0)
Now checking (0, 2)
Already visited: (0, 2)
Start DFS for Pacific from (0, 1)
Now checking (0, 1)
Already visited: (0, 1)
Start DFS for Pacific from (0, 2)
Now checking (0, 2)
Already visited: (0, 2)
---Check last row---
Start DFS for Atlantic from (3, 0)
Now checking (3, 0)
Visiting: (3, 0), height: 6 >= prev_height: 6
Now checking (2, 0)
Cannot flow from 6 to lower height 2 at (2, 0)
Now checking (4, 0)
Out of bounds: (4, 0)
Now checking (3, -1)
Out of bounds: (3, -1)
Now checking (3, 1)
Cannot flow from 6 to lower height 4 at (3, 1)
Start DFS for Atlantic from (3, 1)
Now checking (3, 1)
Visiting: (3, 1), height: 4 >= prev_height: 4
Now checking (2, 1)
Cannot flow from 4 to lower height 3 at (2, 1)
Now checking (4, 1)
Out of bounds: (4, 1)
Now checking (3, 0)
Already visited: (3, 0)
Now checking (3, 2)
Visiting: (3, 2), height: 5 >= prev_height: 4
Now checking (2, 2)
Cannot flow from 5 to lower height 1 at (2, 2)
Now checking (4, 2)
Out of bounds: (4, 2)
Now checking (3, 1)
Already visited: (3, 1)
Now checking (3, 3)
Out of bounds: (3, 3)
Start DFS for Atlantic from (3, 2)
Now checking (3, 2)
Already visited: (3, 2)
---Check first column---
Start DFS for Pacific from (0, 0)
Now checking (0, 0)
Already visited: (0, 0)
Start DFS for Pacific from (1, 0)
Now checking (1, 0)
Already visited: (1, 0)
Start DFS for Pacific from (2, 0)
Now checking (2, 0)
Visiting: (2, 0), height: 2 >= prev_height: 2
Now checking (1, 0)
Already visited: (1, 0)
Now checking (3, 0)
Visiting: (3, 0), height: 6 >= prev_height: 2
Now checking (2, 0)
Already visited: (2, 0)
Now checking (4, 0)
Out of bounds: (4, 0)
Now checking (3, -1)
Out of bounds: (3, -1)
Now checking (3, 1)
Cannot flow from 6 to lower height 4 at (3, 1)
Now checking (2, -1)
Out of bounds: (2, -1)
Now checking (2, 1)
Visiting: (2, 1), height: 3 >= prev_height: 2
Now checking (1, 1)
Already visited: (1, 1)
Now checking (3, 1)
Visiting: (3, 1), height: 4 >= prev_height: 3
Now checking (2, 1)
Already visited: (2, 1)
Now checking (4, 1)
Out of bounds: (4, 1)
Now checking (3, 0)
Already visited: (3, 0)
Now checking (3, 2)
Visiting: (3, 2), height: 5 >= prev_height: 4
Now checking (2, 2)
Cannot flow from 5 to lower height 1 at (2, 2)
Now checking (4, 2)
Out of bounds: (4, 2)
Now checking (3, 1)
Already visited: (3, 1)
Now checking (3, 3)
Out of bounds: (3, 3)
Now checking (2, 0)
Already visited: (2, 0)
Now checking (2, 2)
Cannot flow from 3 to lower height 1 at (2, 2)
Start DFS for Pacific from (3, 0)
Now checking (3, 0)
Already visited: (3, 0)
---Check last column---
Start DFS for Atlantic from (0, 2)
Now checking (0, 2)
Visiting: (0, 2), height: 5 >= prev_height: 5
Now checking (-1, 2)
Out of bounds: (-1, 2)
Now checking (1, 2)
Cannot flow from 5 to lower height 4 at (1, 2)
Now checking (0, 1)
Cannot flow from 5 to lower height 2 at (0, 1)
Now checking (0, 3)
Out of bounds: (0, 3)
Start DFS for Atlantic from (1, 2)
Now checking (1, 2)
Visiting: (1, 2), height: 4 >= prev_height: 4
Now checking (0, 2)
Already visited: (0, 2)
Now checking (2, 2)
Cannot flow from 4 to lower height 1 at (2, 2)
Now checking (1, 1)
Visiting: (1, 1), height: 4 >= prev_height: 4
Now checking (0, 1)
Cannot flow from 4 to lower height 2 at (0, 1)
Now checking (2, 1)
Cannot flow from 4 to lower height 3 at (2, 1)
Now checking (1, 0)
Cannot flow from 4 to lower height 3 at (1, 0)
Now checking (1, 2)
Already visited: (1, 2)
Now checking (1, 3)
Out of bounds: (1, 3)
Start DFS for Atlantic from (2, 2)
Now checking (2, 2)
Visiting: (2, 2), height: 1 >= prev_height: 1
Now checking (1, 2)
Already visited: (1, 2)
Now checking (3, 2)
Already visited: (3, 2)
Now checking (2, 1)
Visiting: (2, 1), height: 3 >= prev_height: 1
Now checking (1, 1)
Already visited: (1, 1)
Now checking (3, 1)
Already visited: (3, 1)
Now checking (2, 0)
Cannot flow from 3 to lower height 2 at (2, 0)
Now checking (2, 2)
Already visited: (2, 2)
Now checking (2, 3)
Out of bounds: (2, 3)
Start DFS for Atlantic from (3, 2)
Now checking (3, 2)
Already visited: (3, 2)
================================================
Pacific reachable cells:
{(0, 1), (1, 2), (2, 1), (0, 0), (3, 1), (1, 1), (2, 0), (3, 0), (0, 2), (1, 0), (3, 2)}
Atlantic reachable cells:
{(1, 2), (2, 1), (3, 1), (1, 1), (3, 0), (0, 2), (2, 2), (3, 2)}
Result cells that can reach both oceans:
Cell (0, 2) can reach both oceans
Cell (1, 1) can reach both oceans
Cell (1, 2) can reach both oceans
Cell (2, 1) can reach both oceans
Cell (3, 0) can reach both oceans
Cell (3, 1) can reach both oceans
Cell (3, 2) can reach both oceans
```
### Time & Space Complexity
- Time: O(m * n)
- m = the number of rows
- n = the number of columns
- 我們從四條邊界出發走 DFS，但因為我們有儲存已訪問的格子，每個格子最多只會被拜訪兩次，一次是 Pacific Ocean 一次是 Atlantic Ocean，所以最多會走 2 * m * n 次 ⟹ O(m * n)
- Space: O(m * n)
- 用 visited set 來儲存走過的格子，所以最壞情況是兩個 set 都存了 m * n 個格子
- 若是一次遞迴到全部的格子，也就是接續呼叫 `dfs` 到所有格子，那 callstack 的深度也會是 m * n
- 因此空間複雜度會是 3 * m * n ⟹ O(m * n)
## Solution 2 - BFS
(working)
### Logic
### Code
### Time & Space Complexity
## Solution 3 - Backtracking
(working)
### Logic
### Code
### Time & Space Complexity
Sign in with Wallet
Connect another wallet