骑士问题

 1 //骑士问题
 2 #include <iostream>
 3 #include <stdio.h>
 4 #include <string.h>
 5 #include <queue>
 6 using namespace std;
 7 int c[9][9];//棋盘
 8 int dir[8][2] = {{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2}};//前进方法
 9 typedef struct
10 {
11     int x,y,count;
12 }node;
13 node start,finish;
14 int bfs()
15 {
16     memset(c,0,sizeof(c));
17     node pre,cur;
18     start.count = 0;
19     queue<node> q;
20     q.push(start);
21     c[start.x][start.y] = 1;
22     while(!q.empty())
23     {
24         pre = q.front();
25         q.pop();
26         if(pre.x == finish.x&&pre.y == finish.y)
27         return pre.count;
28         for(int i = 0; i < 8; i++)
29         {
30             cur.x = pre.x + dir[i][0];
31             cur.y = pre.y + dir[i][1];
32             if(cur.x<1||cur.x>8||cur.y<1||cur.y>8)continue;
33             if(c[cur.x][cur.y]==1)continue;
34             c[cur.x][cur.y] = 1;
35             cur.count = pre.count + 1;
36             q.push(cur);
37         }
38     }
39     return -1;
40 }
41 int main()
42 {
43     char row,end;
44     int col,ed;
45     int min;  
46     while(scanf("%c",&row)!=EOF)
47     {
48         scanf("%d",&col);
49         getchar();
50         scanf("%c%d",&end,&ed);
51         getchar();
52         start.x = row-'a'+1;
53         start.y = col;
54         finish.x = end-'a'+1;
55         finish.y = ed;
56         if(start.x==finish.x&&start.y==finish.y)
57         min = 0;
58         else  min = bfs();
59         printf("To get from %c%d to %c%d takes %d knight moves.
",row,col,end,ed,min);
60     }
61     return 0;
62 }
View Code