复试上机准备之马跳棋

Author Avatar
Patrick 3月 06, 2019

题目要求

假设国际象棋棋盘有 5*5 共 25 个格子。设计一个程序,使棋子从初始位置(棋盘编号 为 1 的位)开始跳马,能够把棋盘的格子全部都走一遍,每个格子只允许走一次。

(1)输出一个如图 2 的解,左上角为第一步起点。

(2)总共有多少解。

P.S 国际象棋的棋子是在格子中间的。国际象棋中的“马走日”,如下图所示,第一步为[1,1], 第二步为[2,8]或[2,12],第三步可以是[3,5]或[3,21]等,以此类推。

分析

这是一个常规的回溯题,要注意的就是一共有八个走的方向,在返回的时候记得还原原本的状态值。

一共有 304 解,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
# include <iostream>

using namespace std;

int arr[5][5] = {0};
int vis_num = 1;
int cnt = 0;

void horse_jump(int x, int y) {
// 输出走法
if (vis_num == 25) {
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) {
cout << arr[i][j] << ' ';
}
cout << endl;
}
cout << endl;
cnt++;
}

// 右二下一
if (x + 2 < 5 && y + 1 < 5 && arr[x + 2][y + 1] == 0) {
arr[x + 2][y + 1] = ++vis_num;
horse_jump(x + 2, y + 1);
// 重置状态
arr[x + 2][y + 1] = 0;
--vis_num;
}
// 右一下二
if (x + 1 < 5 && y + 2 < 5 && arr[x + 1][y + 2] == 0) {
arr[x + 1][y + 2] = ++vis_num;
horse_jump(x + 1, y + 2);
// 重置状态
arr[x + 1][y + 2] = 0;
--vis_num;
}
// 左二上一
if (x - 2 >= 0 && y - 1 >= 0 && arr[x - 2][y - 1] == 0) {
arr[x - 2][y - 1] = ++vis_num;
horse_jump(x - 2, y - 1);
// 重置状态
arr[x - 2][y - 1] = 0;
--vis_num;
}
// 左一上二
if (x - 1 >= 0 && y - 2 >= 0 && arr[x - 1][y - 2] == 0) {
arr[x - 1][y - 2] = ++vis_num;
horse_jump(x - 1, y - 2);
// 重置状态
arr[x - 1][y - 2] = 0;
--vis_num;
}
// 左二下一
if (x - 2 >= 0 && y + 1 < 5 && arr[x - 2][y + 1] == 0) {
arr[x - 2][y + 1] = ++vis_num;
horse_jump(x - 2, y + 1);
// 重置状态
arr[x - 2][y + 1] = 0;
--vis_num;
}
// 左一下二
if (x - 1 >= 0 && y + 2 < 5 && arr[x - 1][y + 2] == 0) {
arr[x - 1][y + 2] = ++vis_num;
horse_jump(x - 1, y + 2);
// 重置状态
arr[x - 1][y + 2] = 0;
--vis_num;
}
// 右二上一
if (x + 2 < 5 && y - 1 >= 0 && arr[x + 2][y - 1] == 0) {
arr[x + 2][y - 1] = ++vis_num;
horse_jump(x + 2, y - 1);
// 重置状态
arr[x + 2][y - 1] = 0;
--vis_num;
}
// 右一上二
if (x + 1 < 5 && y - 2 >= 0 && arr[x + 1][y - 2] == 0) {
arr[x + 1][y - 2] = ++vis_num;
horse_jump(x + 1, y - 2);
// 重置状态
arr[x + 1][y - 2] = 0;
--vis_num;
}
}


int main() {
arr[0][0] = 1;
horse_jump(0, 0);
cout << cnt << endl;

return 0;
}