給你一個由整數組成的 m*n 方陣，你必須要寫個程式，來計算出「重量」（ weight ） 最小的路線。每條路線都是從第一直行的任何一格做為起點，走了若干步之後，至第 n 行（最後一行）的其中一格為終點。所謂的一步就是從第 i 行走至第 i+1 行，其中移動的時候只能走到原本的或是相鄰的一橫列（也就是走平的或是斜一格）。另外要注意的是，第一橫列和最後一橫列（第 m 列）也算是相鄰的，也可以這樣想，就是整個方陣是上下「包」起來的，看起來像一個倒著的圓柱體。總之，對於任何一格能夠走的下一步就如下圖所示：
所謂一個路徑的「重量」（weight）就是此路徑經過的 n 個格子裡，它們的整數總和。舉個例子，下面有兩個不同的5*6 方陣。（實際上你可以注意到它們的不同只在最後一列而已）
這兩個方陣的「最小重量路徑」（ 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 貓
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||