TopCoder

FHVirus
$\Huge 8e7 二分圖判斷範例程式碼有錯,道歉!$

User's AC Ratio

80.4% (41/51)

Submission's AC Ratio

37.1% (63/170)

Tags

Description

在 $M \cdot N$ 的土地上,降下了相當多的雨水。

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

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

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

Input Format

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

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

接下來有 $M$ 列每列有 $N$ 個整數,第 $i$ 列第 $j$ 行的整數 $h_{ij}$ 代表 $(i,j)$ 位置的高度。

值得注意的是,水只會往東西南北四個方向流,並且所有高度值都介於 $0$ 和 $2 ^ {31}-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