Preparing NOJ

马的Hamilton周游路线问题

20000ms 81920K

Description:

8x8的国际象棋棋盘上的一只马,恰好走过除起点外的其它63 个位置各一次最后回到起点。这条路线称为一条马的Hamilton 周游路线。对于给定的mxn的国际象棋棋盘,m和n均为大于5 的偶数,且|m-n|≤2,试设计一个分治算法找出一条马的Hamilton周游路线对于给定的偶数m,n≥6,且|m-n|≤2,编程计算m´n 的国际象棋棋盘一条马的Hamilton周游路线。

Input:

输入的第1行有2个正整数m和n,表示给定的国际象棋棋盘由m行,每行n个格子组成。

Output:

用下面的2种表达方式输出马的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

Note:

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1209

Tags

Submitted 5

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet