马踏棋盘（基于栈的深搜算法实现）
简单来说，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径，这就是马踏棋盘的简单描述。
话不多说，代码如下，要是有什么不懂的地方，欢迎讨论~
|
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
|
#include <stdio.h>#include <stdlib.h>#define M 8 //行#define N 8 //列 typedef struct snode //坐标{ int flag; int x; int y;}stack;typedef struct node { int top; //记录走了多少步top+1 int flag; //记录上一步走的方向 stack * p; //路径栈}LNode; LNode * CreateStacke(); //创建，并初始化void Judge(LNode * s, int chess[][N]); //判断往哪走void Push(LNode * s, stack x); //入栈操作void Pop(LNode * s); //出栈操作int IsFull(LNode * s); //判满int IsEmpty(LNode * s); //判空 int main(){ int chess[M][N] = {0}; //棋盘 int i, j; //循环变量 LNode * step; //step存的是走的路径 step = CreateStacke(); Judge(step, chess); for (i = 0; i < N; i++){ for (j = 0; j < M; j++){ printf("%2d ", chess[i][j]); } printf("\n"); } return 0;}LNode * CreateStacke(){ LNode * s = (LNode *)malloc(sizeof(LNode)); if (!s){ printf("内存空间不足!\n"); system("pause"); exit(0); } s->p = (stack *)malloc(sizeof(stack) * M * N); if (!s->p){ printf("内存空间不足!\n"); system("pause"); exit(0); } s->top = -1; // 把top放在栈底 return s;}void Judge(LNode * s, int chess[][N]) { int ch[8][2] = { //马可能走的八个方向 {1, -2}, { 2, -1}, {2, 1 }, { 1, 2 }, {-1, 2}, {-2, 1 }, {-2, -1},{-1, -2} }; int i, j = 1, flag = 1; stack t; printf("请输入马的初始位置：(%d * %d)\n", M, N); scanf("%d%d", &t.y, &t.x); if (t.x <= 0 || t.x > N || t.y <= 0 || t.y > N){ printf("输入的坐标超出范围！\n"); exit(0); } t.x--; t.y--; chess[t.y][t.x] = 1; //选择马的第一个落脚点 Push(s, t); while (s->top < M * N - 1 && s->top != -1){ for (i = 0; i < 8; i++){ t.x = s->p[s->top].x + ch[i][0]; t.y = s->p[s->top].y + ch[i][1]; //如果它的坐标没有超出范围，并且没有走过，则把该路线存入路径栈 if (t.x >= 0 && t.y >= 0 && t.x < N && t.y < M && !chess[t.y][t.x]){ if(flag){ //没有退回去 Push(s, t); chess[t.y][t.x] = s->top + 1; s->p[s->top - 1].flag = i; flag = 1; break; } else{ //退回去了 if (s->p[s->top].flag < i){ //重新走时，让它的方向不等于原先的方向 flag = 1; } } } } //如果没有能走的路时，即，所有的路径都超出范围，或者，该位置已经走过了，则，退到上一步，重新选择； if (i == 8){ chess[s->p[s->top].y][s->p[s->top].x] = 0; Pop(s); flag = 0; } }}void Push(LNode * s, stack x){ if (IsFull(s)){ printf("栈上溢，不能进行入栈操作!\n"); exit (0); } else{ s->top++; s->p[s->top] = x; }}void Pop(LNode * s){ if (IsEmpty(s)){ printf("栈为空，不能进行出栈操作!\n"); exit(0); } s->top--;}int IsFull(LNode * s){ if (s->top >= M * N){ return 1; } else{ return 0; }}int IsEmpty(LNode * s){ if (s->top == -1){ return 1; } else{ return 0; }} |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/Vivid_110/article/details/41548343
