1402 . 淹水問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

77.8% (42/54)

Submission's AC Ratio

35.7% (65/182)

Tags

CKsum 2008-CKsum-4th

Description

在 M⋅N 的土地上，降下了相當多的雨水。

水會往低處流，也會在低處積水。

一旦水越過了邊界，就會流到外面去。

請問這樣的地形最多能夠累積多少單位的水量呢？

Input Format

輸入檔可能包含多筆測試資料。

每一筆測試資料的第一列有兩個正整數 M,N(1≤M,N≤500)。

接下來有 M 列每列有 N 個整數，第 i 列第 j 行的整數 hij 代表 (i,j) 位置的高度。

值得注意的是，水只會往東西南北四個方向流，並且所有高度值都介於 0 和 231−1 之間（包含）。

Output Format

對於每筆測試資料請輸出一個整數代表該地形降雨時可以累積的最大水量。

Sample Input 1

5 5
5 5 5 5 5
5 0 0 0 5
5 0 0 0 5
5 0 0 0 5
5 5 5 5 1

3 3
5 5 5
5 0 0
5 5 5

3 3
1 1 1
1 5 1
1 1 1

Sample Output 1

45
0
0

Hints

Problem Source

原TIOJ1402 / 快樂暑假營第四次練習比賽。Problem Setter：Tmt。

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
Submit
Back to Top