c100: Unidirectional TSP

出處

http://zerojudge.tw/ShowProblem?problemid=c100

內容 ：

給你一個由整數組成的 m*n 方陣，你必須要寫個程式，來計算出「重量」（ weight ） 最小的路線。每條路線都是從第一直行的任何一格做為起點，走了若干步之後，至第 n行（最後一行）的其中一格為終點。所謂的一步就是從第 i 行走至第 i+1 行，其中移動的時候只能走到原本的或是相鄰的一橫列（也就是走平的或是斜一格）。另外要注意的是，第一橫列和最後一橫列（第 m 列）也算是相鄰的，也可以這樣想，就是整個方陣是上下「包」起來的，看起來像一個倒著的圓柱體。總之，對於任何一格能夠走的下一步就如下圖所示：

這兩個方陣的「最小重量路徑」（ minimal-weight path ）已經在上面分別標出來了。注意一下右邊的方陣，其利用了第一列和最後一列是相鄰的這個性質達到了最小的重量。

輸入說明 ：

輸入裡包含多組測試資料，每組代表一個方陣。每組測試資料的第一列為2個正整數 m 與 n （1 <= m <=10，1 <= n <= 100），依序表示這方陣有幾橫列和幾直行。而後就是 m*n 個整數，這些整數是按照「列順序」（ row major order ）來排列，也就是輸入裡的前 n 個數表示方陣的第一橫列，再下來的 n 個數表示第二橫列，依此類推。在輸入裡，同一列的數彼此間將會被一個以上的空白隔開。值得注意的是，這裡說的整數並不一定是正的。輸入以及計算的過程所出現的數均不會超過長整數（long）的範圍。

Sample Input中前2組測試資料所表達的方陣就是上方的2個圖，請參考。

輸出說明 ：

對於每個方陣，你必須輸出兩列東西。第一列是「最小重量路徑」（ minimal-weight path ），第二列則是其「重量」。對於第一列，你必須輸出 n 個正整數，依序表示在每一行，此路徑經過了第幾列。如果存在兩個以上的路徑其「重量」皆為最小，則輸出按照字典順序（ lexicographically ）最小的那一個路徑。請參考Sample Output。

範例輸入 ：

5 6

3 4 1 2 8 6

6 1 8 2 7 4

5 9 3 9 9 5

8 4 1 3 2 6

3 7 2 8 6 4

5 6

3 4 1 2 8 6

6 1 8 2 7 4

5 9 3 9 9 5

8 4 1 3 2 6

3 7 2 1 2 3

2 2

9 10 9 10

範例輸出 ：

1 2 3 4 4 5

16

1 2 1 5 4 5

11

1 1

19

提示 ：

* 中文翻譯：Lucky 貓

出處 ：

ACM 116

解題策略

從最右邊倒數第二行開始，與倒數第一行三個方向相加值最小者，紀錄值與來自於的方向。再看倒數第三行與第二行，一直到第一行為止，接著找第一行最小的就是解。