1038 . 2025C班第一階段認證考_pC

Submit out of contest
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

roychuang

User's AC Ratio

60.0% (3/5)

Submission's AC Ratio

36.8% (7/19)

Tags

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

Sample Output 1

5 2 2 2
5 1 1 1
5 1 1 1

Sample Input 2

1 5
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 65536 65536 1 2 3
1 2000 65536 65536 1 2 3
2 2000 65536 65536 1 2 3
3 2000 65536 65536 1 2 3
4 2000 65536 65536 1 2 3
5 2000 65536 65536 1 2 3
6 2000 65536 65536 1 2 3
7 2000 65536 65536 1 2 3
8 2000 65536 65536 1 2 3
9 2000 65536 65536 1 2 3
10 2000 65536 65536 1 2 3
11 2000 65536 65536 1 2 3
12 2000 65536 65536 1 2 3
13 2000 65536 65536 1 2 3
14 2000 65536 65536 1 2 3
15 2000 65536 65536 1 2 3
16 2000 65536 65536 1 2 3
17 2000 65536 65536 1 2 3
18 2000 65536 65536 1 2 3
19 2000 65536 65536 1 2 3
20 2000 65536 65536 2 3
21 2000 65536 65536 2 3
22 2000 65536 65536 2 3
23 2000 65536 65536 2 3
24 2000 65536 65536 2 3
25 2000 65536 65536 2 3
26 2000 65536 65536 2 3
27 2000 65536 65536 2 3
28 2000 65536 65536 2 3
29 2000 65536 65536 2 3
30 2000 65536 65536 2 3
31 2000 65536 65536 2 3
32 2000 65536 65536 2 3
33 2000 65536 65536 2 3
34 2000 65536 65536 2 3
35 2000 65536 65536 2 3
36 2000 65536 65536 2 3
37 2000 65536 65536 2 3
38 2000 65536 65536 2 3
39 2000 65536 65536 2 3
40 2000 65536 65536 2 3
41 2000 65536 65536 2 3
42 2000 65536 65536 2 3
43 2000 65536 65536 2 3
44 2000 65536 65536 3
45 2000 65536 65536 3
46 2000 65536 65536 3
47 2000 65536 65536 3
48 2000 65536 65536 3
49 2000 65536 65536 3
50 2000 65536 65536 3
51 2000 65536 65536 3
52 2000 65536 65536 3
53 2000 65536 65536 3
54 2000 65536 65536 3
55 2000 65536 65536 3
56 2000 65536 65536 3
57 2000 65536 65536 3
58 2000 65536 65536 3
59 2000 65536 65536 3
60 2000 65536 65536 3
61 2000 65536 65536 3
62 2000 65536 65536 3
63 2000 65536 65536 3
64 2000 65536 65536 3
65 2000 65536 65536 3
66 2000 65536 65536 3
67 2000 65536 65536 3
Submit out of contest
Back to Top