你所任職的公司專門製造用來撿垃圾的機器人,每當機器人被指派到一個工作前,會先把場地的配置圖轉成網格輸入到電腦中,每個場地可以視為一平面,在圖上會標出所有垃圾所在的格子。機器人會從最西北角的格子開始走,走到最東南角的格子為止,然而在每一次的移動中只能向東或南方移動一格。
機器人會沿著格子把垃圾蒐集起來,直到到達終點所在的最東南方格子,便不能再被重新利用。基於所用的花費將會與機器人數成正比,你對於「如何最有效率的使用」之類的問題感興趣,因此,你的任務便是要用單一一個機器人經過的路徑上蒐集最多的垃圾數。
當然符合這樣條件的路徑就會有許多種,你的程式便必須輸出總共有幾條這樣的路徑會撿到最多的垃圾數。你的機器人能不占任何空間的清除路上所及的垃圾.一組合法的路徑輸出將會是沿路上所經之垃圾格子的編號順序.
上圖為一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)的格子點
&&答案中任意一數都不會超過2147483647
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
CASE#1: 5 4 CASE#2: 4 1
(1)aDorable Panda
(2)Delicious Pancake
(3)Damn Panchiao senior high school
2010/5/28偷偷的加強了測資~~(敬請見諒
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」
|