机器博弈中的数据结构与基本方法（二）-----递归及回溯法实例
1、跳马问题：从左上角开始，按照象棋中马的行走规则（但是不考虑马脚，只需要按日字走），要求每个点走一次且仅一次，并且所有的点走走到，求解所有可行走法。
思路及代码：
1 #include <cstdio>
2 int a[9][9]; //包含边界拓展
3 int S = 0; //总的方案数
4 void PrintAnswer(){ //打印行走策略
5 printf("Answer\t%d\n", S);
6 for (int i = 2; i < 7; i++){
7 for (int j = 2; j < 7; j++){
8 printf("%-4d\t", a[i][j]);
9 }
10 printf("\n");
11 }
12 }
13 void Try(int i, int ml, int nl);
14 void Move(int i, int m, int n){
15 if (0 == a[m][n]){
16 a[m][n] = i;
17 if (i < 25){
18 Try(i+1, m, n);
19 } else {
20 S++;
21 PrintAnswer();
22 }
23 a[m][n] = 0;
24 }
25 }
26 void Try(int i, int ml, int nl){ //i：到达结点编号，ml/nl出发点的位置
27 int n, m;
28 m = ml - 2;
29 n = nl + 1; //走法 1
30 Move(i, m, n);
31
32 m = ml - 2;
33 n = nl - 1; //走法 2
34 Move(i, m, n);
35
36 m = ml + 2;
37 n = nl + 1; //走法 3
38 Move(i, m, n);
39
40 m = ml + 2;
41 n = nl - 1; //走法 4
42 Move(i, m, n);
43
44 m = ml - 1;
45 n = nl + 2; //走法 5
46 Move(i, m, n);
47
48 m = ml - 1;
49 n = nl - 2; //走法 6
50 Move(i, m, n);
51
52 m = ml + 1;
53 n = nl + 2; //走法 7
54 Move(i, m, n);
55
56 m = ml + 1;
57 n = nl - 2; //走法 8
58 Move(i, m, n);
59 }
60 int main(int argc, char const *argv[])
61 {
62 freopen("ans.txt", "w", stdout);
63 for (int i = 0; i < 9; i++){
64 for (int j = 0; j < 9; j++){
65 if (i < 2 || i > 6 || j < 2 || j > 6){
66 a[i][j] = -1;
67 } else {
68 a[i][j] = 0;
69 }
70 }
71 }
72 a[2][2] = 1;
73 Try(2, 2, 2);
74 return 0;
75 }
ans.cpp
部分答案
1 Answer 301
2 1 6 17 12 25
3 16 11 2 7 18
4 3 20 5 24 13
5 10 15 22 19 8
6 21 4 9 14 23
7 Answer 302
8 1 16 7 12 25
9 8 13 2 17 6
10 3 20 15 24 11
11 14 9 22 5 18
12 21 4 19 10 23
13 Answer 303
14 1 18 7 12 25
15 8 13 2 19 6
16 3 20 17 24 11
17 14 9 22 5 16
18 21 4 15 10 23
19 Answer 304
20 1 8 19 14 25
21 18 13 2 9 6
22 3 20 7 24 15
23 12 17 22 5 10
24 21 4 11 16 23
25 共 304 种策略
部分答案
图示
2、迷宫问题：如下图，求出所有可以到达出口的路径（左上角绿色是入口，右下角是出口，深红色部分是墙，红色是为了编程方便（边界判断）人为加的）。
代码及思路
1 #include <cstdio>
2 int a[8][12];
3 int s = 0;
4 void PrintPath(){
5 printf("Path%d\n", s);
6 for (int i = 1; i < 7; i++){
7 for (int j = 1; j < 11; j++)
8 {
9 printf("%4d", a[i][j]);
10 }
11 printf("\n");
12 }
13 }
14 void Try(int i, int ml, int nl);
15 void Move(int i, int m, int n){
16 if (0 == a[m][n]){
17 a[m][n] = i;
18 if (6 == m && 10 == n){
19 s++;
20 PrintPath();
21 } else {
22 Try(i+1, m, n);
23 }
24 a[m][n] = 0;
25 }
26 }
27
28 void Try(int i, int ml, int nl){
29 int m, n;
30 m = ml;
31 n = nl - 1; //注意只能上下左右与移动
32 Move(i, m, n);
33
34 m = ml;
35 n = nl + 1;
36 Move(i, m, n);
37
38 m = ml - 1;
39 n = nl;
40 Move(i, m, n);
41
42 m = ml + 1;
43 n = nl;
44 Move(i, m, n);
45 }
46 int main(int argc, char const *argv[])
47 {
48 freopen("ans.txt", "w", stdout);
49 for (int i = 0; i < 8; i++){
50 for (int j = 0; j < 12; j++){
51 a[i][j] = -1;
52 }
53 }
54 a[1][1] = 0;
55 for (int i = 1; i <= 8; i++){
56 if (2!=i && 5!=i){
57 a[2][i] = 0;
58 }
59 }
60 for (int i = 1; i <= 9; i++){
61 if (4!=i && 5!=i && 7!=i){
62 a[3][i] = 0;
63 }
64 }
65 for (int i = 1; i <= 9; i++){
66 if (2!=i && 3!=i && 7!=i && 8!=i){
67 a[4][i] = 0;
68 }
69 }
70 for (int i = 1; i <= 9; i++){
71 if (5!=i){
72 a[5][i] = 0;
73 }
74 }
75 a[6][9] = a[6][10] = 0;
76 a[1][1] = 1;
77 Try(2, 1, 1);
78 printf("Sum = %d\n", s);
79 return 0;
80 }
ans.cpp
输出结果
Path1
1 -1 -1 -1 -1 -1 -1 -1 -1 -1
2 -1 0 0 -1 13 14 15 -1 -1
3 0 0 -1 -1 12 -1 16 17 -1
4 -1 -1 9 10 11 -1 -1 18 -1
5 6 7 8 -1 0 0 0 19 -1
-1 -1 -1 -1 -1 -1 -1 -1 20 21
Path2
1 -1 -1 -1 -1 -1 -1 -1 -1 -1
2 -1 0 0 -1 0 0 0 -1 -1
3 0 0 -1 -1 0 -1 0 0 -1
4 -1 -1 9 10 11 -1 -1 0 -1
5 6 7 8 -1 12 13 14 15 -1
-1 -1 -1 -1 -1 -1 -1 -1 16 17
Sum = 2
输出结果
图示
