UVa439(骑士的移动)

这道题主要是写一个图的遍历。因为题目中要求是最短路径，所以采用的是宽度优先遍历。本来是想缩短运行时间而采用头尾同时使用bfs算法，但奈何个人水平有限而未能实现。所以本题代码中使用就是最直接的bfs算法。由于写这段代码时比较匆忙，所以代码应该还有较大的优化空间。

  1 #include  
  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 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