看到这道题，第一个想法就是“搜索”！“回溯”！的确，这种思路是很正确的，BFS和DFS都可以来解决：
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
int dx[12]= {-2,-2,-1,1,2,2,2,2,1,-1,-2,-2},
dy[12]= {-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};
int main() {
int s[101][101],que[10000][4]= {0},x1,y1,x2,y2;
memset(s,0xff,sizeof(s)); //s数组的初始化
int head=1,tail=1; //初始位置入队
que[1][1]=1;
que[1][2]=1;
que[1][3]=0;
cin>>x1>>y1>>x2>>y2; //读入黑马和白马的出发位置
while(head<=tail) { //若队列非空，则扩展队首结点
for(int d=0; d<=11; d++) { //枚举12个扩展方向
int x=que[head][1]+dx[d]; //计算马按d方向跳跃后的位置
int y=que[head][2]+dy[d];
if(x>0&&y>0)
if(s[x][y]==-1) { //若（x,y）满足约束条件
s[x][y]=que[head][3]+1; //计算(1,1)到(x,y)的最少步数
tail++; //（1,1）至（x,y）的最少步数入队
que[tail][1]=x;
que[tail][2]=y;
que[tail][3]=s[x][y];
if(s[x1][y1]>0&&s[x2][y2]>0) { //输出问题的解
cout<<s[x1][y1]<<endl;
cout<<s[x2][y2]<<endl;
system("pause");
return 0;
}
}
}
head++;
}
return 0;
}
咱们来模拟以下队列的操作：
首先，初始化一个队列（拿脑子想出了一个队列……），然后，定义头指针head和尾指针tail都为1。
如果尾指针在head的位置上或者head的前面，则这个queue不是空的或者这个队列中的元素还没有完全处理完。
相反，判断一个队列是否为空或者其中的元素是否全部处理完毕，那就可以用 tail > head 来判断了。
当有新的元素加入进来，旧的元素不要就可以tail+1，尾指针向上移一位。
当然，你也可以用STL的序列式容器queue，也是根据个人习惯的。
但是……
这道题有个bug。
我们不妨来倒推，它要去(1,1)这个点，我们就从(1,1)这个点去(x,y)这个位置。
当我们统计每一个坐标点都能走几步能到达时，得到了这个图：
可以看出当行数和列数都小于等于5的时候是没有规律的，但当行数和列数是大于5的时候，是以两个为单位依次递增，也就是第六、第七列是3，第八、第九列是4，第十、第十一是5……然后再在1到5之内特判一下，就可以得到了：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
int x,y,k;
for(int i=1;i<=2;i++)
{
cin>>x>>y;
if(x<=5&&y<=5)
{
if((x==1&&y>=2&&y<=5)||(y==1&&x>=2&&x<=5)||(x==5&&y>=1&&y<=5)||(y==5&&x>=1&&x<=5)||x==2&&y==4||x==4&&y==2||x==4&&y==4)
printf("2");
if(x==2&&y==2||x==4&&y==3||x==3&&y==4)
printf("3");
if(x==3&&(y>=2&&y<=3)||x==2&&y==3)
printf("1");
if(x==1&&y==1)
printf("0");
}
else
{
for(int i=6,k=3;i<=max(x,y);i+=2,k++)
{
if(max(x,y)==i)
printf("%d ",k);
}
}
}
return 0;
}