马的Hamilton周游路线问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

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

Input

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

Output

将计算出的马的Hamilton周游路线用下面的2种表达方式输出。第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

Hint

Source