TopCoder

Thumb 1
羽瀨川小鷹
我是布丁

User's AC Ratio

75.0% (24/32)

Submission's AC Ratio

34.5% (38/110)

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

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

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 (KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1