1402 . 淹水問題
TopCoder
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
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
0
0
Hints
Problem Source
原TIOJ1402 / 快樂暑假營第四次練習比賽。Problem Setter：Tmt。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |