这道题主要是写一个图的遍历。因为题目中要求是最短路径，所以采用的是宽度优先遍历。本来是想缩短运行时间而采用头尾同时使用bfs算法，但奈何个人水平有限而未能实现。所以本题代码中使用就是最直接的bfs算法。由于写这段代码时比较匆忙，所以代码应该还有较大的优化空间。
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 /*******************
6 UVa439 骑士的移动
7 *******************/
8
9 struct Node{
10 //x1列 x2行 k是走到这个点需要的步数
11 int x1, x2, k;
12 Node(int x = 0, int y = 0, int weight = 0):x1(x), x2(y), k(weight){}
13 bool equal(Node& n){
14 return (x1 == n.x1 && x2 == n.x2);
15 }
16 };
17
18 int k = 0;
19 int buf[7][7];
20 queue<Node> q1;
21
22 int char_to_int(char ch){
23 return ch-96;
24 }
25
26 //寻找下一个位置并且将结构体入队并且修改棋盘访问状态
27 int next(Node& n, Node& end){
28 if(n.x1 + 2 <= 8 && n.x2 + 1 <= 8 && !buf[n.x2][n.x1 + 1]){
29 Node n1(n.x1 + 2, n.x2 + 1, n.k+1);
30 if(n1.equal(end)){
31 printf("%d", n1.k);
32 return 1;
33 }else{
34 q1.push(n1);
35 buf[n1.x2-1][n1.x1-1] = 1;
36 }
37 }
38 if(n.x1 + 1 <= 8 && n.x2 + 2 <= 8 && !buf[n.x2 + 1][n.x1]){
39 Node n1(n.x1 + 1, n.x2 + 2, n.k+1);
40 if(n1.equal(end)){
41 printf("%d", n1.k);
42 return 1;
43 }else{
44 q1.push(n1);
45 buf[n1.x2-1][n1.x1-1] = 1;
46 }
47 }
48 if(n.x1 - 1 >= 1 && n.x2 + 2 <= 8 && !buf[n.x2 + 1][n.x1 - 2]){
49 Node n1(n.x1 - 1, n.x2 + 2, n.k+1);
50 if(n1.equal(end)){
51 printf("%d", n1.k);
52 return 1;
53 }else{
54 q1.push(n1);
55 buf[n1.x2-1][n1.x1-1] = 1;
56 }
57 }
58 if(n.x1 - 2 >= 1 && n.x2 + 1 <= 8 && !buf[n.x2][n.x1 - 3]){
59 Node n1(n.x1 - 2, n.x2 + 1, n.k+1);
60 if(n1.equal(end)){
61 printf("%d", n1.k);
62 return 1;
63 }else{
64 q1.push(n1);
65 buf[n1.x2-1][n1.x1-1] = 1;
66 }
67 }
68 if(n.x1 + 1 <= 8 && n.x2 - 2 >= 1 && !buf[n.x2 - 3][n.x1]){
69 Node n1(n.x1 + 1, n.x2 - 2, n.k+1);
70 if(n1.equal(end)){
71 printf("%d", n1.k);
72 return 1;
73 }else{
74 q1.push(n1);
75 buf[n1.x2-1][n1.x1-1] = 1;
76 }
77 }
78 if(n.x1 + 2 <= 8 && n.x2 - 1 >= 1 && !buf[n.x2 - 2][n.x1 + 1]){
79 Node n1(n.x1 + 2, n.x2 - 1, n.k+1);
80 if(n1.equal(end)){
81 printf("%d", n1.k);
82 return 1;
83 }else{
84 q1.push(n1);
85 buf[n1.x2-1][n1.x1-1] = 1;
86 }
87 }
88 if(n.x1 - 1 >= 1 && n.x2 - 2 >= 1 && !buf[n.x2 -3][n.x1 - 2]){
89 Node n1(n.x1 - 1, n.x2 - 2, n.k+1);
90 if(n1.equal(end)){
91 printf("%d", n1.k);
92 return 1;
93 }else{
94 q1.push(n1);
95 buf[n1.x2-1][n1.x1-1] = 1;
96 }
97 }
98 if(n.x1 - 2 >= 1 && n.x2 - 1 >= 1 && !buf[n.x2 - 2][n.x1 - 3]){
99 Node n1(n.x1 - 2, n.x2 - 1, n.k+1);
100 if(n1.equal(end)){
101 printf("%d", n1.k);
102 return 1;
103 }else{
104 q1.push(n1);
105 buf[n1.x2-1][n1.x1-1] = 1;
106 }
107 }
108 return 0;
109 }
110
111 void solve(Node n1, Node n2){
112
113 for(;;){
114 //寻找下一个位置
115 if(next(n1, n2)){
116 break;
117 }else{
118 n1 = q1.front(); q1.pop();
119 continue;
120 }
121 }
122 return;
123 }
124
125 int main()
126 {
127 char x = 0;
128 int y = 0;
129 memset(buf, 0, sizeof(buf));
130
131 //输入起使位置
132 cin >> x;
133 cin >> y;
134 Node start = Node(char_to_int(x), y, 0);
135 buf[y-1][char_to_int(x)-1] = 1;
136 //输入终止位置
137 cin >> x;
138 cin >> y;
139 Node end = Node(char_to_int(x), y, 0);
140 if(start.equal(end)){
141 printf("0");
142 return 0;
143 }
144 solve(start, end);
145 return 0;
146 }
这段代码的主要思路就是使用bfs算法遍历图，同时记录走到该点需要的最短步数，当遍历过程中发现遍历到了终点，就打印步数，并且退出程序。整段代码并不复杂，其中最长的next()函数反而是最直观的。
运行结果如下：
a1
b2
4
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
