d524. 10599 - Robots(II)
Tags :
Accepted rate : 55人/73人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-11-27 17:36

Content

你所任職的公司專門製造用來撿垃圾的機器人,每當機器人被指派到一個工作前,會先把場地的配置圖轉成網格輸入到電腦中,每個場地可以視為一平面,在圖上會標出所有垃圾所在的格子。機器人會從最西北角的格子開始走,走到最東南角的格子為止,然而在每一次的移動中只能向東或南方移動一格。

機器人會沿著格子把垃圾蒐集起來,直到到達終點所在的最東南方格子,便不能再被重新利用。基於所用的花費將會與機器人數成正比,你對於「如何最有效率的使用」之類的問題感興趣,因此,你的任務便是要用單一一個機器人經過的路徑上蒐集最多的垃圾數。

當然符合這樣條件的路徑就會有許多種,你的程式便必須輸出總共有幾條這樣的路徑會撿到最多的垃圾數。你的機器人能不占任何空間的清除路上所及的垃圾.一組合法的路徑輸出將會是沿路上所經之垃圾格子的編號順序.
雖然你的機器人不能清除不包含垃圾的格子,但若你希望的話,你能設定你的機器人經過某些特定的點但不清除其上的垃圾.

 

 

上圖為一6x7的網格,格子從左往右、從上到下依序編號1、2、3、4、……、42,上圖範例的最大垃圾收集數為5並有4種不同的可行路徑包含:<2, 4, 11, 13, 28><2, 4, 11, 13, 41><2, 4, 11, 25, 28><2, 4, 11, 25, 41>

 其中編號2,4,11,13,25,28,41對應平面座標(1,2),(1,4),(2,4),(2,6),(4, 4),(4, 7),(6, 7)的格子點

Input
每組輸入為一場地配置圖,第一行為一對整數表示場地的大小n和m(n,m<=100),讀到-1,-1表結束輸入,接下來的幾行會有多對的整數,每兩個整數自成一行表示被垃圾佔據的格子座標,讀到0,0即為表對一張場地配置圖的描述結束,且同一個點不會被重複標記成包含垃圾兩次或兩次以上.
Output
對於每一組測資先輸出數字對應第幾組的輸入,接著輸出整數代表機器人所能收集的最大垃圾數K,及所有能收集該垃圾數的路徑數,皆下來的K個整數請列舉出其中任意一種的可行路徑。上述任兩個整數間皆以一個空白格開。ps:由於出題者本身不會用SPECIAL JUDGE的緣故,在ZERO JUDGE submit時就直接輸出:CASE#輸出序號:最大蒐集數<空格>總路徑數<換行>

&&答案中任意一數都不會超過2147483647

Sample Input #1
6 7
1 2
1 4
2 4
2 6
4 4
4 7
6 6
0 0
4 4
1 1
2 2
3 3
4 4
0 0
-1 -1
Sample Output #1
CASE#1: 5 4
CASE#2: 4 1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :

(1)aDorable Panda

(2)Delicious Pancake

(3)Damn Panchiao senior high school

2010/5/28偷偷的加強了測資~~(敬請見諒 

Tags:
出處:
UVa10599 [管理者: pcshic (PCSHIC) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」