回分類題庫
d050: 4.貨物集中問題
關鍵字: 100年彰雲嘉區複賽

測資點 : 2 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 214 Times / 207 Users | Submit : 382 Times / 223 Users | Accepted rate : 93%
題目加入時間 : 2012-07-06 14:47

Content: 简体中文

一個矩形平面大型倉儲空間,共有R×C個分區,其中R代表矩形的列數,C代表矩形的C行數。此倉儲空間以一R×C二維矩陣表示,倉儲空間中的每一分區以二維座標表示,二維矩陣中每一分區的內容代表各分區的儲存貨物量。今因整個倉儲空間保養維修的因素,需將所有分區的貨物暫時集中於某一分區內,並假設任一分區的容量均可以容納目前倉儲空間中的總貨物容量。因為貨物移動需要移動成本,假定一個單位的貨物從現在的分區移動到相鄰上下左右任意一個分區的成本為100元,請寫一程式決定貨物應該集中於那一分區,其整體移動成本為最小。

範例:以上圖為例,倉儲空間分割成3×4個分區,每一個分區以座標表示。另、每一分區內的數字代表該分區現有的儲存貨物量。如右圖,第(1,1)分區有4單位貨物,而(1,3), (2,1), (2,4),(3,2), (3,3)分區均無貨物。

Input:

測試資料第一列有一個整數N,代表測試資料有幾組。
第二列有兩個數字 R, C, (1<=R, C<=100)分別代表第一組測試資料的二維矩陣列數與行數。接下來的R 列,每一列有C 個整數,這R列中的第i 列的第j 個整數代表 (i, j) 區的儲存貨物量。每兩個整數之間都會有一個空白隔開。

Output:

第一列請輸出每一組測試資料貨物應該集中於那一分區 (i, j),方能使其整體移動成本最小,以兩個整數表示,整數間以一個空白區隔。
第二列請輸出其所需要的最小成本。

Sample Input:help

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

Sample Output :

1 2
2400

Hint :

Author :

100年彰雲嘉區複賽 (管理員:sagit)

  Solve it!   Status Forum