a562: ITSA201112 P2 小白鼠走方格
Tags :
Accepted rate : 77人/97人 ( 79% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-10-25 18:52

Content

在生物研究的世界裡,小白鼠是一個很常被實驗室用來做實驗的動物之一。因為小鼠的體型小,實驗操作容易,而且易於繁殖,生命週期不會太長,在實驗進行上比其他物種,例如:靈長類,是個更好的選擇。但醫學研究上,小鼠與人類還是有一定程度的差異,並不是每一種疾病都可以找到適合的研究模式,有些情況與人類截然不同。

今天我們要做一個實驗,把一隻小白鼠放在一個m * m的方陣上任一個格子裡 (如下圖),觀察小白鼠可能的最長移動路徑。

[ 2  1  1 25 63]
[ 7  7  2 24 24]
[24 19  1 12  1]
[13 23  1 13  2]
[12  8 57 42  1]

小白鼠的移動方式有三個條件
1. 小白鼠可以垂直或是水平移動,不能對角移動。
2. 走過的方格不可以再走。
3. 移動路徑裡的數字皆不相同。
假設小白鼠被放在最左上角的位置(方格2),可能的最長移動路徑為紅字部分 (非唯一解),距離為13。
給你一個方陣請你寫一個程式算出小白鼠可能的最長移動路徑是多少。

Input
第一列有1個整數n,代表接下來有n組測試資料。每組測試資料的第一列,有一個整數 m(0 < m <= 8),代表這方陣的邊長大小。接下來有m列,每列有 m 個整數(均介於 0 到 100 之間)代表方陣中的數字,數字間以空格隔開。每組測試資料有一空白列隔開。
Output
輸出每筆測試資料的解答,每組解答以空白列隔開。
Sample Input #1
2
4
1 3 5 7
2 11 6 9
6 13 8 2
8 17 10 4
3
1 2 3
1 2 4
1 2 3
Sample Output #1
13
4
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 30.0s , <1M
Hint :
Tags:
出處:
ITSA201112 [管理者:
morris1028 (碼畜)
]


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