Problem1370--国际象棋--马踏棋盘问题

1370: 国际象棋--马踏棋盘问题

Time Limit: 10000000 Sec  Memory Limit: 128 MB
Submit: 13  Solved: 3
[Submit] [Status] [Web Board] [Creator:]

Description

国际象棋的棋盘为8×8的方格棋盘。现将“马”放在任意指定的方格中,按照“马”走棋的规则将“马”进行移动。要求每个方格只能进入一次,最终使得“马”走遍棋盘的64个方格。
编写一个程序,实现马踏棋盘操作,要求用1〜64这64个数字标注马移动的路径,也就是按照求出的行走路线,将数字1,2,……64依次填入棋盘的方格中,并输出。
国际象棋中,“马”的移动规则如下所示。
   ○     ○   
 ○         ○ 
     ●     
 ○         ○ 
   ○     ○   

图中实心的圆圈代表“马”的位置,它下一步可移动到图中空心圆圈所标注的8个位置上,该规则叫做“马走日”。

但是如果“马”位于棋盘的边界附近,那么它下一步可移动到的位置就不一定有8个了,因为要保证“马”每一步都走在棋盘中。

马踏棋盘的问题其实就是要将1,2,……,64填入到一个8×8的矩阵中,要求相邻的两个数按照“马”的移动规则放置在矩阵中。

例如数字a放置在矩阵的(i,j)位置上,数字a+1只能放置在矩阵的

(i-2,j+1),(i-1,j+2),(i+1,j+2),(i+2,j+1),(i+2,j-1),(i+1,j-2),(i-1,j-2),(i-2,j-1)
之中的一个位置上。将矩阵填满并输出。

这样在矩阵中从1,2……遍历到64,就得到了马踏棋盘的行走路线。因此本题的最终目的是输出一个8*8的矩阵,

在该矩阵中填有1, 2……64这64个数字,相邻数字之间遵照“马走日”的规则。

程序要求输入马初始的位置,输出8*8的矩阵,表示马的移动过程。
如果马能够走遍所有的格子,输出矩阵,然后输出一句话The horse has travelled the chess borad
如果马不能够走遍所有的格子,输出一句话The horse cannot travel the chess board
例如:输入
2 0 1
其中,2 0表示马一开始的坐标是(2,0),1表示第一步。
输出
43   50   47   38   57   52   61   32
48   37   44   51   46   33   58   53
1    42   49   56   39   60   31   62
36   15   40   45   34   29   54   59
41   2    35   16   55   24   63   30
14   5    12   9    22   19   28   25
3    10   7    20   17   26   23   64
6    13   4    11   8    21   18   27
The horse has travelled the chess borad



Input

2 0 1

Output

43   50   47   38   57   52   61   32
48   37   44   51   46   33   58   53
1    42   49   56   39   60   31   62
36   15   40   45   34   29   54   59
41   2    35   16   55   24   63   30
14   5    12   9    22   19   28   25
3    10   7    20   17   26   23   64
6    13   4    11   8    21   18   27
The horse has travelled the chess borad

Sample Input

2 0 1

Sample Output

43   50   47   38   57   52   61   32
48   37   44   51   46   33   58   53
1    42   49   56   39   60   31   62
36   15   40   45   34   29   54   59
41   2    35   16   55   24   63   30
14   5    12   9    22   19   28   25
3    10   7    20   17   26   23   64
6    13   4    11   8    21   18   27
The horse has travelled the chess borad

HINT

本题不要求提交到OJ系统,本地环境验证通过即可。


Source/Category

 

[Submit] [Status]