回分類題庫
d090: 6.馬步問題
關鍵字: 106年台中區複賽

測資點 : 5 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 78 Times / 63 Users | Submit : 178 Times / 71 Users | Accepted rate : 89%
題目加入時間 : 2018-09-06 13:58

Content: 简体中文

象棋中馬走動的方法是直橫並行,即先橫向或直向走一格,然後再直向或橫向走兩格。如下圖範例,位於棋盤中間的馬,走一步時可以到達的位置(8種)

 

給定棋盤的大小 3×n,寬為3列、長為n行,假設馬從棋盤的左上角出發,是否可走到棋盤上的任意一格?n=3時3×3方格中走訪順序如下表,棋盤內的數字代表棋子馬走的順序,中間方格無法到達,故無解。

 

n=4時3×4方格中走訪順序如下表,可以走完。

 

其走法可能不只一種,另一個走法如下表

 

當有多個答案時,請先將這3n的格子所代表的解排成一維陣列後,由左至右依字典排序(lexicographical order)比較,再挑選字典排序最小的一個方法輸出。所謂字典排序法,對於兩個一維陣列 1 2 4 5 3和1 2 5 4 3,先由左邊第一位開始比較,左邊第一位都是1,不能分辨大小;則再比左邊第二位,都是2;再比左邊第三位,後者是5較大,所以後者排列較大,其後的幾位也不用再比較,亦即1 2 4 5 3小於1 2 5 4 3。

於n=4馬步走法的輸出兩種方法中,左邊第五位資料比較時第一個方法為8比第二個方法的12小,故輸出第一個。

 

n=7時3×7方格走訪順序有以下

 

等16種走法。 

Input:

一個大於或等於3且小於或等於10的正整數 (3<=n<=10)

Output:

若無法走訪3×n棋盤上的任一格則輸出0,若可以走訪3×n棋盤的任一格,則輸出找到所有可能的走法中字典排序 (lexicographical order) 最小的一個方法。將每一格被走訪的順序,共有3×n個數字輸出於同一列,數字間以一個空格分開。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
輸入1:
3

輸入2:
4

輸入3:
7

Sample Output :

輸出1:
0

輸出2:
1 4 7 10 8 11 2 5 3 6 9 12

輸出3:
1 4 7 18 15 10 13 6 19 2 9 12 21 16 3 8 5 20 17 14 11

Hint :

Author :

106年台中區複賽 (管理員:sagit)

  Solve it!   Status Forum