【题解】Knight Moves-C++

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 string o1,o2;
 4 int sx,sy,ex,ey,cnt;
 5 int dir[8][2]={{1,2},{1,-2},{-1,{2,1},{-2,-1},-1}};
 6 struct node
 7 {
 8     int x,y,t;
 9     node(){};
10     node(int xx,int yy,int tt)
11     {
12         x=xx,y=yy,t=tt;
13     }
14 };
15 bool vis[10][10];
16 bool in(int x,int y)
17 {
18     return 1<=x&&x<=8&&1<=y&&y<=8;
19 }
20 void bfs()
21 {
22     queue<node> q;
23     q.push(node(sx,0));
24     vis[sx][sy]=0;
25     while(!q.empty())
26     {
27         node now=q.front();
28         q.pop();
29         if(now.x==ex&&now.y==ey)
30         {
31             cout<<"To get from "<<o1<<" to "<<o2<<" takes "<<now.t<<" knight moves."<<endl;
32             return;
33         }
34         for(int i=0;i<8;i++)
35         {
36             int tx=now.x+dir[i][0],ty=now.y+dir[i][1];
37             if(in(tx,ty)&&!vis[tx][ty])
38             {
39                 q.push(node(tx,ty,now.t+1));
40                 vis[tx][ty]=1;
41             }
42         }
43     }
44     cout<<"f**k"<<endl;
45     return;
46 }
47 int main()
48 {
49     while(cin>>o1>>o2)
50     {
51         memset(vis,0,sizeof(vis));
52         sx=o1[0]-‘a‘+1,sy=o1[1]-‘0‘;
53         ex=o2[0]-‘a‘+1,ey=o2[1]-‘0‘;
54         bfs();
55     }
56     return 0;
57 }