回分類題庫
g070: E.傘兵
關鍵字: NPSC 2010 國中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 70 Times / 55 Users | Submit : 133 Times / 64 Users | Accepted rate : 86%
題目加入時間 : 2012-01-13 16:35

Content: 简体中文

「報告將軍,有緊急狀況。」
「說!」
「前線遭遇伏擊,兄弟們死傷慘重,請求補給與增援。」
「嗯· · ·」
「將軍!我們不能白白讓他們送死啊!」
「· · · · · ·」
「將軍!」
「好吧,派出傘兵中隊空降支援前線!」

你的任務來了:
你手上有前線區域的地圖,地圖劃分為 R × C 的小格子。我們用(r, c)代表由北向南數來第 r 排,由西向東數來第 c 個小格子。你不知道前線部隊確切的位置,因為那是最高機密,不過你確定他們一定在地圖上的某處。然而,由於地形、天候、敵人視線等等因素,不是地圖上的每個地方都可以空降傘兵。可以空降的地方共有 N 個,座標分別是(r1, c1), (r2, c2), · · · , (rN, cN)。

空降在每個的地方都有一些風險,用 v1, v2, · · · , vN 表示,值越大代表風險越高。空降下去的傘兵會知道前線部隊的確切位置,並且會往那個位置移動。傘兵可以從一個小格子移動到上下左右相鄰的小格子,而且每移動一格都會增加 1 單位的風險。這整個支援任務的總風險就是空降的風險加上傘兵移動的風險。

請你利用地圖和可以空降的地方的資料,算出派傘兵到地圖上每個地方的最小總風險。

Input:

第一行有一個整數T,代表接下來有幾組測試資料。兩筆測試資料中間會以一個空行隔開。

每一筆的第一行有 R C N 三個整數,意思如題目所述。接下來有 N 行,每行有三個整數 ri ci vi ,代表第 i 個可以空降的地方的座標和風險。

Output:

請對每筆測試資料輸出 R 行,每行有 C 個數字,第 r 行第 c 個數字代表派傘兵到(r, c) 支援的最小總風險。兩個數字間請用一個空白隔開,兩筆測試資料間也請用一個空行隔開。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
3 3 1
2 2 5

2 2 2
1 1 9
2 1 4

Sample Output :

7 6 7
6 5 6
7 6 7

5 6
4 5

Hint :

Author :

NPSC 2010 國中組初賽 (管理員:sagit)

  Solve it!   Status Forum