棋

/*BFS学习*/
#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

char chx,chy;
int sx,sy,tx,ty;
int head,tail,ans;
int fx[9]={0,1,-1,1,-1,2,-2,2,-2},
    fy[9]={0,2,2,-2,-2,1,-1,-1,1};
bool go,map[10][10];

struct node_ans_que
{
    int x,y,step;
}que[1000*1000];

struct node_from_que
{
    int x,y;
}q[1000*1000];

int main()
{
    cin>>chx>>sy;  sx=chx-96;
    cin>>chy>>ty;  tx=chy-96;
    map[sx][sy]=1;
    que[tail].x=sx,que[tail].y=sy,que[tail++].step=0;
    int step=0;
    q[step].x=sx,q[step].y=sy;
    while(head<tail)
    {
        int x=que[head].x,y=que[head].y;step=que[head].step;
        
        for(int i=1;i<=8;i++)
        {
            int xx=x+fx[i];
            int yy=y+fy[i];
            if(xx==tx&&yy==ty&&!map[tx][ty])
            {
                go=1;
                ans=step+1;
            }
            if(go)    break;
            if(xx>0&&xx<9&&yy>0&&yy<9)
                if(!map[xx][yy])
                {
                    map[xx][yy]=1;
                    que[tail].x=xx;
                    que[tail].y=yy;
                    que[tail++].step=step+1;
                    q[step].x=x,q[step].y=y;
                }
        }
        if(go)    break;
        head++;
    }
    q[ans].x=tx,q[ans].y=ty;
    for(int i=0;i<=ans;i++)
    {
        char ch=q[i].x+96;
        cout<<ch<<q[i].y<<" ";
    }
    cout<<endl;
    cout<<"To get from "<<chx<<sy<<" to "<<chy<<ty<<" take "<<ans<<" knight moves."<<endl;
    return 0;
}

 1 #include <queue>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 struct QueueNodeType {
10     int x,y,step;
11 };
12 
13 const int dx[9]={0,-2,-1,1,2,2,1,-1,-2};
14 const int dy[9]={0,1,2,2,1,-1,-2,-2,-1};
15 
16 int sx,sy,ex,ey,ans,from[10][10][2];
17 
18 bool map[10][10];
19 
20 queue<struct QueueNodeType>que;
21 
22 struct QueueNodeType node(int x,int y,int step)
23 {
24     struct QueueNodeType nod;
25     nod.x=x,nod.y=y,nod.step=step;
26     return nod;
27 }
28 
29 void path(int x,int y)
30 {
31     if(from[x][y][0]&&from[x][y][1]) path(from[x][y][0],from[x][y][1]);
32     cout<<char(x+96)<<' '<<y<<endl;
33     return ;
34 }
35 
36 int main()
37 {
38     char ch;
39     int num;
40     cin>>ch>>num;
41     sx=ch-'a'+1,sy=num;
42     cin>>ch>>num;
43     ex=ch-'a'+1,ey=num;
44     que.push(node(sx,sy,0));
45     map[sx][sy]=true;
46     while(!que.empty())
47     {
48         bool if_break=false;
49         struct QueueNodeType pos=que.front();
50         for(int i=1;i<=8;i++)
51         {
52             if(pos.x+dx[i]>0&&pos.x+dx[i]<=8&&pos.y+dy[i]>0&&pos.y+dy[i]<=8)
53             {
54                 if(pos.x+dx[i]==ex&&pos.y+dy[i]==ey)
55                 {
56                     from[pos.x+dx[i]][pos.y+dy[i]][0]=pos.x;
57                     from[pos.x+dx[i]][pos.y+dy[i]][1]=pos.y;
58                     ans=pos.step+1;
59                     if_break=true;
60                     break;
61                 }
62                 if(!map[pos.x+dx[i]][pos.y+dy[i]])
63                 {
64                     map[pos.x+dx[i]][pos.y+dy[i]]=true;
65                     from[pos.x+dx[i]][pos.y+dy[i]][0]=pos.x;
66                     from[pos.x+dx[i]][pos.y+dy[i]][1]=pos.y;
67                     que.push(node(pos.x+dx[i],pos.y+dy[i],pos.step+1));
68                 }
69             }
70         }
71         if(if_break) break;
72         que.pop();
73     }
74     cout<<"To get from "<<char(sx+'a'-1)<<sy<<" to "<<char(ex+'a'-1)<<ey<<"takes "<<ans<<" knight moves."<<endl;
75     path(ex,ey);
76     return 0;
77 }

升级版

——每当你想要放弃的时候，就想想是为了什么才一路坚持到现在。