-
Notifications
You must be signed in to change notification settings - Fork 8
Expand file tree
/
Copy pathHorseUsingStack.cpp
More file actions
147 lines (128 loc) · 3.06 KB
/
HorseUsingStack.cpp
File metadata and controls
147 lines (128 loc) · 3.06 KB
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
#include <stdio.h>
#include <stack>
using namespace std;
/*马走日*/
const int N = 5; //棋盘行数跟列数
int matrix[N][N] = {0}; //表示棋盘
int solution = 0;//解的个数
int count = 0; //第几步
int move[8][2]={{-1,-2},{-2,-1}, {-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};//八个方向
//注意find这一步当前层的的结点，结点的坐标不是x与y，而通过Node中的x与y与direction三者计算后得到当前层的结点
struct Node
{
int x;
int y;
int direction;
};
//在棋盘范围内，而且可放棋
bool IsOk(Node node)
{
int x, y;
x = node.x + move[node.direction][0];
y = node.y + move[node.direction][1];
if(( x <= N-1 ) && (x >=0 )
&& (y <= N-1 ) && (y >=0 )
&& (matrix[x][y]==0 ))
{
return true;
}
else
{
return false;
}
}
//打印
void Print()
{
printf("第%d种解：\n",++solution);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
printf("%3d",matrix[i][j]);
}
printf("\n");
}
printf("-----------------\n");
}
void DFS()
{
Node node;
stack<Node> stack;
int x, y;
count = 1;
node.x = 0;
node.y = 0;
node.direction = 0;
matrix[0][0] = count++;
stack.push(node);
node.direction = 0;
stack.push(node);
while(stack.size() >= 2)
{
//--find
node = stack.top();
while (node.direction < 8 && !IsOk(node))
{
node.direction++;
}
if (node.direction < 8)
{
//--forward
if (count < N * N)
{
//把ok的节点放到当前层
stack.pop();
stack.push(node);
x = node.x + move[node.direction][0];
y = node.y + move[node.direction][1];
matrix[x][y] = count++;
//进入下一层的第一个节点
node.x = x;
node.y = y;
node.direction = 0;
stack.push(node);
}
else
{
//--done
//打印出结果;
x = node.x + move[node.direction][0];
y = node.y + move[node.direction][1];
matrix[x][y] = count++;
Print();
//注意先清除当前结点的数据
matrix[x][y] = 0;
count--;
//进入当前层的下一个结点;
node.direction++;
stack.pop();
stack.push(node);
}
}
else
{
//----back
//返回上一层当前结点的下一个节点
stack.pop();
if (stack.size() == 1)
{
return;
}
node = stack.top();
//注意先清除当前结点的数据
x = node.x + move[node.direction][0];
y = node.y + move[node.direction][1];
matrix[x][y] = 0;
count--;
node.direction++;
stack.pop();
stack.push(node);
}
}
}
int main()
{
DFS();
return 0;
}