1038 . 2025C班第一階段認證考_pC
Description
Water Flow
小明是一位熱愛冒險的探險家，最近他發現了一片神秘的地圖。這張地圖上標示了每個地區的海拔高度，形成了一個 $N \times M$ 的二維陣列。據說，這片地圖隱藏著一個奇特的自然現象——水流的軌跡會揭示出地形的秘密。
傳說中，水在這片地圖上總是遵循一個規律：它會從所在的格子流向 8 連通方向（上下左右與對角線）中高度比自己低且最低的那一格，並且只會往更低的地方移動，直到停在某個局部最低點。這些最低點被稱為「水窪」，是地圖的關鍵所在。
小明決定解開這個謎團。他希望能知道，如果將水倒在每個格子上，水最終會停在哪個格子，並以此形成一張新的地圖，標示出每個格子最終流向的高度值。
你能幫助小明完成這項挑戰嗎？
Input Format
第一行包含兩個整數 $N$ 和 $M$，分別表示地圖的行數和列數，其中 $1 \leq N, M \leq 150$。
接下來的 $N$ 行，每行包含 $M$ 個整數，表示地圖上每個格子的海拔高度 $H_{i,j}$。
海拔高度可能很高但必定是正數，也就是 $1 \leq H_{i,j} \leq 10 ^ {18}$，請使用long long int做儲存，其中保證海拔高度不會重複。
- 本題有Bonus (50 pts)。Bonus 比較困難，建議有時間再寫。
Output Format
輸出一個 $N \times M$ 的二維陣列，表示每個格子最終流向的高度值。
Sample Input 1
3 4
12 9 3 2
5 10 7 6
11 8 1 4
12 9 3 2
5 10 7 6
11 8 1 4
Sample Output 1
5 2 2 2
5 1 1 1
5 1 1 1
5 1 1 1
5 1 1 1
Sample Input 2
1 5
1 4 5 2 3
1 4 5 2 3
Sample Output 2
1 1 2 2 2
Hints
Sample Input #1 中：
$12 \to 5$ (沒有更低點了)
$10 \to 7 \to$ 1 (沒有更低點了)
$9 \to 3 \to 2$ (沒有更低點了)
依此類推。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~19 | 一維陣列，保證 $N = 1$ | 60 |
| 2 | 0~43 | 無其他特殊限制 | 40 |
| 3 | 0~67 | $1 \leq N, M \leq 1000$。Bonus 比較困難，建議有時間再寫 | 50 |