2180 . 勇者冒險 (Adventure)
TopCoder
Description
冒險者萊恩在新手村訓練即將屆滿一年，他詢問師父，什麼時候才能離開新手村，到外面的世界冒險。師父聽聞，拿出一張世界地圖，用手指了地圖的一個位置。
「萊恩，我們在這裡，這是新手村。你想到哪裡去呢?」
萊恩很興奮地說，「聽說迷霧森林很刺激，我想去那裡看看。」
師父又用手指了地圖上另一個位置，「這裡就是迷霧森林。」接著，師父在地圖上雙手揮舞，地圖上開始浮現許多數字。
「哇，好酷喔！師父，這些數字是什麼意思!」
「沒有數字的區域代表無法橫跨的沙漠，數字代表可行經區域裡的怪物等級；如果冒險者的等級低於怪物等級，是沒辦法活著通過那個區域的。」
「啊？！」萊恩很仔細地看著地圖，慢慢地用手指帶出一條路線。「我如果從新手村往北走，再往東走，這樣說起來，我得把我的等級提升到 $5$ 級，才能到得了迷霧森林了。」
目前等級只有 $4$ 級的萊恩低下頭。
「別急，萊恩，看看這裡。」師父抓著萊恩的手指，你可以先往東走，再往北走，然後往西抵達迷霧森林。這條路線，$4$ 級的你就能辦到了。」
「喔耶！謝謝師父！」
真實冒險世界的地圖很大，需要你的幫忙。請你寫一個程式，給定地圖尺寸、新手村和迷霧森林的位置，以及地圖上區域的怪物等級，計算出萊恩最少需要幾等級，才能從新手村出發，安全抵達迷霧森林。
Input Format
- 第一行有兩個正整數 $R$ 和 $C$ ($1 \leq R, C \leq 1000$),代表地圖有幾列與幾行。
- 第二行有四個整數 $R_s$, $C_s$, $R_d$, $C_d$ ($0 \leq R_s, R_d < R,0 \leq C_s, C_d < C$),其中 $(R_s, C_s)$ 代 表新手村的位置，$(R_d, C_d)$ 代表迷霧森林的位置。新手村和迷霧森林很安全，裡面必定沒有怪物。新手村和迷霧森林不會在同一個位置。
- 第三行有一個整數 $N$ $(0 \leq N \leq R\times C$),代表地圖中有幾個可以行經的區域。
- 接下去有 $N$ 行,第 $i$ 行有三個整數值 $R_i$, $C_i$, $L_i$ ($0 \leq R_i < R,0 \leq C_i < C,0 \leq L_i \leq 10^ 9$)，分別代表區域座標和該區域怪物等級。
- 輸入中，任兩個整數間以一個空白隔開。
Output Format
輸出萊恩最少需要為幾等級，才能從新手村出發，平安抵達迷霧森林。（測試資料保
證存在至少一條從新手村到迷霧森林的路。）
Sample Input 1
6 5
1 1 4 3
18
0 0 2
0 1 3
1 0 1
1 2 1
1 3 4
1 4 2
2 0 3
2 1 2
2 4 4
3 1 3
3 2 5
3 3 2
3 4 3
4 1 3
4 2 5
4 4 2
5 2 2
5 3 2
Sample Output 1
Sample Input 2
0 1 1 3
10
2 0 5
2 1 4
2 2 2
2 3 1
1 0 5
1 1 7
1 2 6
0 0 5
0 2 9
0 3 8
Sample Output 2
Hints
本題共有三組測試資料：
第一組測試資料 $1 \leq R, C \leq 10$，新手村到迷霧森林只存在一條路徑，共 $46$ 分。
第二組測試資料 $1 \leq R, C \leq 100$，共 $23$ 分。
第三組測試資料 $1 \leq R, C \leq 1000$，共 $31$ 分。
Problem Source
107北市賽
testdata set by Omelet
110/2/1 修正測資、微調時限及rejudge
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~9 | $1 \leq R, C \leq 10$，新手村到迷霧森林只存在一條路徑 | 46 |
| 2 | 0~19 | $1 \leq R, C \leq 100$ | 23 |
| 3 | 0~29 | $1 \leq R, C \leq 1000$ | 31 |