蔡子经数据结构6.13

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 100
int G[MAXN][MAXN];//表示棋盘
//我是实在没想到这个遍历方向的前后竟然对效率影响这么大
//int dir[8][2] = {
// {1,2},{2,1},
// {2,-1},{1,-2},
// {-1,-2},{-2,-1},
// {-1,2},{-2,1}
// };
int dir[8][2]={
{1,2},{2,1},
{2,-1},{1,-2},
{-1,-2},{-2,-1},
{-2,1},{-1,2}
};
int n = 8, m = 8;//8行8列的棋盘
int path[65][3];

void print()
{
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
printf("%d ",G[i][j]);
}
puts("");
}
puts("");
}

void dfs(int x, int y, int cnt)
{
if(cnt == n*m)
{
// print();
for(int i = 0; i < cnt; ++i)
{
printf("%d %d %d\n",path[i][0],path[i][1],path[i][2]);
}
exit(0);
}
int tx,ty;
for(int k = 0; k < 8; ++k)
{
tx = x + dir[k][0];
ty = y + dir[k][1];
if(tx < 0 || ty < 0 || tx >= n || ty >= m) continue;
if(G[tx][ty]) continue;
G[tx][ty] = cnt+1;
path[cnt][0] = tx;
path[cnt][1] = ty;
path[cnt][2] = cnt-1;
dfs(tx, ty, cnt+1);
G[tx][ty] = 0;
}
return ;
}

int main()
{
memset(path, 0, sizeof(path));
memset(G, 0, sizeof(G));
G[0][0] = 1;
path[0][0] = 0;
path[0][1] = 0;
path[0][2] = -1;
dfs(0,0,1);
return 0;
}