2011年12月17日 星期六

11202 - The least possible effort

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

原文出處

沒有留言:

張貼留言