Background
下圖為在一個8x8的棋盤上將西洋棋的「騎士」由1, 2, 3, ... 64的順序依序移動棋子，並使每一格剛好只經過一次的其中一種可能的移動方式。
在不同起點下，會有相同的移步方式，基於對稱性，上圖中的1, 26, 54, 7就會有相同的移步方式，只要找到其中一組解就可以輕易地找出另外三組解。
本題探討當棋盤非必然為正方形的情況。
The Problem
給定一個 n x m 的棋盤(6 <= n, m <= 10000)，請找出最少需要對幾個不同的起點做搜尋，以找出所有可能的騎士移步方式。下圖顯示基於對稱性，同一顏色的位置只需要搜尋一次，我們並不需要對每個不同的起點逐一尋找。
The Input
輸入資料的第一列有一整數 t 表示測試資料的組數，接下來每組資料一列共有兩個以空白字元隔開的整數 6 <= n, m <= 10000，分別表示棋盤為 n 列 m 行。The Output
請對每組測試資料，輸出所有騎士的移步方式最少需要對幾個起點作搜尋。Sample Input
3 6 9 15 10 7 13
Sample Output
15 40 28
原文出處
沒有留言:
張貼留言