昨晚自己写了一个递归回溯算法，结果爆栈了， 今早参考了书本的单源最短路径算法，过了~~
感觉过的有些勉强，那个每个点都记录自己的路径信息，感觉太费空间，费劲不讨好
昨晚写代码时，一些错误：
定义一个struct里面不能包含自己的struct，即不能自己包含自己，只能用指向自己指针，再动态分配
把一个二维数组当参数传入函数时， 函数的参数不能是 **指针的指针，受一维数组的影响（一维数组传入，函数函数可以是指针），导致出错了
有几种方式：
int a[10][10];
sum(a);
sum声明可以这样
int sum(int [][10]);//后面括号一定要有数字
int sum(int (*a) [10]);//意思是 a是一个指向有10个元素的int数组的指针
c primer plus上有这样的说明：
一般地， 声明N维数组的指针时，除了最左边的方括号可以留空之外，其他都需要填写数值
附上代码
Knight Moves
1
2
3 #include <iostream>
4 using namespace std;
5 #define NUM 8
6 int a[NUM*NUM][NUM*NUM];
7 bool found[NUM*NUM];
8
9
10 void ininte();
11 int choosepoint(int*);
12 void foundshorstpath(int*, int);
13
14 int main()
15 {
16 ininte();
17 int a1, a2;
18 char b1, b2;
19 int begin;
20
21 int distance[NUM*NUM];
22 //freopen("test.txt","r",stdin);
23
24 while(cin >> b1 >> a1 >> b2 >> a2)
25 {
26 begin = (NUM)*(b1-'a')+a1-1;
27 foundshorstpath(distance, begin);
28 cout << "To get from " << b1 << a1
29 << " to " << b2 << a2
30 << " takes " << distance[(NUM)*(b2-'a')+a2-1]
31 <<" knight moves."<< endl;
32 }
33
34 return 0;
35 }
36 //查找从begin开始点到所有顶点的最短距离
37 //distance就是记录begin开始点到各个顶点的最小距离
38 void foundshorstpath(int* distance, int begin)
39 {
40 int u;
41 int n = NUM*NUM;
42 for (int i = 0; i < n; i++)
43 {
44 found[i] = false;
45 distance[i] = a[begin][i];
46 }//初始化
47
48 found[begin] = true;
49 distance[begin] = 0;
50
51 //开始查找
52 //found就是记录是否查找过的点
53 for (int i = 0; i < n - 2; i++)
54 {
55 u = choosepoint(distance);//查找没有搜索过的距离开始点最小的点
56 found[u] = true;
57 //当添加一个点到已查找的集合时
58 //之前查找到的距离最小的点不一定是最小的
59 //判断当前加入的点，是否鼻之前查找过的最小距离更小
60 for (int w = 0; w < n; w++)
61 {
62 if (!found[w])//判断查找过的
63 {
64 if (distance[u] + a[u][w] < distance[w])
65 distance[w] = distance[u] + a[u][w];
66 }
67 }
68 }
69 }
70
71 int choosepoint(int* distance)
72 {
73 int min = 10000;
74 int minpos = -1;
75 int n = NUM*NUM;
76 for (int i = 0; i < n; i++)
77 {
78 if (distance[i] < min && !found[i])
79 {
80 min = distance[i];
81 minpos = i;
82 }
83 }
84 return minpos;
85 }
86
87 //初始化各个顶点信息
88 //题目是8*8的棋盘，共有8*8个顶点
89 //a是64*64的矩阵，棋盘每一个点都为一个row，每个row都记录它到别的顶点的距离
90 //开始时，把每个点的距离都弄到尽量大，代表他们两个点之间没法到达
91 void ininte()
92 {
93 int n = NUM*NUM;
94
95 for (int i = 0; i < n; i++)
96 {
97 for (int j = 0; j < n; j++)
98 {
99 a[i][j] = 1000;
100 }
101 }
102 //查找马在棋盘每个点所能走的顶点
103 //注意马是走日字的
104 for (int i = 0; i < NUM; i++)
105 {
106 for (int j = 0; j < NUM; j++)
107 {
108 if (i+1 < NUM && j + 2 < NUM)
109 {
110 a[i*NUM + j][(NUM)*(i+1) + j+2 ] = 1;
111 }
112 if (i-1 >= 0 && j + 2 < NUM)
113 {
114 a[i*NUM + j][(NUM)*(i-1) + j+2 ] = 1;
115 }
116 if (i+1 < NUM && j - 2 >= 0)
117 {
118 a[i*NUM + j][(NUM)*(i+1) + j-2 ] = 1;
119 }
120 if (i-1 >= 0 && j - 2 >= 0)
121 {
122 a[i*NUM + j][(NUM)*(i-1) + j-2 ] = 1;
123 }
124 if (i+2 < NUM && j+1 < NUM)
125 {
126 a[i* NUM +j][(NUM)*(i+2) + j+1 ] = 1;
127 }
128 if (i+2 < NUM && j-1 >= 0)
129 {
130 a[i*NUM + j][(NUM)*(i+2) + j-1 ] = 1;
131 }
132 if (i-2 >= 0 && j+1 < NUM)
133 {
134 a[i*NUM + j][(NUM)*(i-2) + j+1 ] = 1;
135 }
136 if (i-2 >= 0 && j-1 >= 0)
137 {
138 a[i*NUM + j][(NUM)*(i-2) + j-1 ] = 1;
139 }
140
141 }
142 }
143 }
顺带附上网上找的比较简便的代码，人家用bfs写的，比我简洁多了
代码
1 #include<iostream>
2 #include<memory>
3 #include<queue>
4 using namespace std;
5
6
7 int dir[8][2]=
8 {{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{-1,2},{-1,-2},{1,-2}
9 }; //八个可能方向
10
11
12 int flag[8][8]; //标记棋盘中一个点是否已经被踏过
13
14
15 struct node
16 {
17 int x,y,step; //棋盘点的坐标和几次可达的信息
18 };
19
20
21 int main()
22 {
23 char a,b,c,d;
24 node N,P;
25 queue<node> Q;
26 memset(flag,0,64);
27 cin>>a>>b>>c>>d;
28 int r1=a-'a';
29 int c1=b-'1';
30 int r2=c-'a';
31 int c2=d-'1';
32 N.x=r1;N.y=c1;N.step=0;
33 Q.push(N); //初始节点入队
34 flag[r1][c1]=1;
35 while(!Q.empty())
36 {
37 N=Q.front();Q.pop(); //出队
38 if(N.x==r2&&N.y==c2) //达到目的，则跳出
39 break;
40 for(int i=0;i<8;i++) //八方向搜索
41 {
42 int tx=N.x+dir[i][0];
43 int ty=N.y+dir[i][1];
44 if(tx>=0&&tx<8&&ty>=0&&ty<8&&flag[tx][ty]==0) //看是否在棋盘内和是否已经被踏过
45 {
46 P.x=tx;P.y=ty;P.step=N.step+1;
47 Q.push(P);
48 flag[tx][ty]=1; //标记为被踏过
49 }
50 }
51 }
52 cout<<"To get from "<<a<<b<<" to "<<c<<d<<' ';
53 cout<<"takes "<<N.step<<" knight moves."<<endl;
54 }