同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

2008_马的Hamilton周游路线

2022-5-16 18:18| 发布者: Hocassian| 查看: 59| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504236387300-Problem List-采集的数据-后羿采集器.html

Pro.ID

2008

Title

马的Hamilton周游路线

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=2008

AC

Submit

Ratio

14.29%

时间&空间限制

Time Limit: 40000/20000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

8×8的国际象棋棋盘上的一只马，恰好走过除起点外的其它63个位置各一次，最后回到起点。这条路线称为一条马的Hamilton周游路线。

对于给定的m×n的国际象棋棋盘，m和n均为大于5的偶数，且 |m-n| ≤ 2，试设计一个分治算法找出一条马的Hamilton周游路线。

对于给定的偶数 6 ≤ m，n ≤ 2046，且|m-n| ≤ 2，计算m×n的国际象棋棋盘一条马的Hamilton周游路线。

输入

输入是两个正整数m和n，表示给定的国际象棋棋盘由m行，每行n个格子组成。

输出

Description

8×8的国际象棋棋盘上的一只马，恰好走过除起点外的其它63个位置各一次，最后回到起点。这条路线称为一条马的Hamilton周游路线。

对于给定的m×n的国际象棋棋盘，m和n均为大于5的偶数，且 |m-n| ≤ 2，试设计一个分治算法找出一条马的Hamilton周游路线。

对于给定的偶数 6 ≤ m，n ≤ 2046，且|m-n| ≤ 2，计算m×n的国际象棋棋盘一条马的Hamilton周游路线。

Input

输入是两个正整数m和n，表示给定的国际象棋棋盘由m行，每行n个格子组成。

Output

将计算出的马的Hamilton周游路线用下面的两种表达方式输出。

第1种表达方式按照马步的次序给出马的Hamilton周游路线。马的每一步用所在的方格坐标(x, y)来表示。x表示行的坐标，编号为0, 1, …, m-1；y表示列的坐标，编号为0, 1, …, n-1。起始方格为(0, 0)。

第2种表达方式在棋盘的方格中标明马到达该方格的步数。(0, 0)方格为起跳步，并标明为第1步。

Sample Input

6 6

Sample Output

(0,0) (2,1) (4,0) (5,2) (4,4) (2,3)
(0,4) (2,5) (1,3) (0,5) (2,4) (4,5)
(5,3) (3,2) (5,1) (3,0) (1,1) (0,3)
(1,5) (3,4) (5,5) (4,3) (3,1) (5,0)
(4,2) (5,4) (3,5) (1,4) (0,2) (1,0)
(2,2) (0,1) (2,0) (4,1) (3,3) (1,2)

1 32 29 18 7 10
30 17 36 9 28 19
33 2 31 6 11 8
16 23 14 35 20 27
3 34 25 22 5 12
24 15 4 13 26 21

Author

John