在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。
他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（100×100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点可能的最少步数。
格式
输入格式
A、B两点的坐标。
输出格式
最少步数。
样例
输入样例
12 16
18 10
输出样例
8
9
#include<bits/stdc++.h>
using namespace std;
//广搜象棋问题
struct Site{
int r,c,s;
};
int dx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2};
int dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};
int main(){
int Step[101][101],que[10000][4]={0},x1,y1,x2,y2;
queue<Site>q;
Site s,news;
memset(Step,0xff,sizeof(Step));//s数组的初始化
s.r=1,s.c=1,s.s=0;
q.push(s);
cin>>x1>>y1>>x2>>y2;//读入白马和黑马的出发位置
while(!q.empty()){//若队列非空，则扩展队首节点
s=q.front();
q.pop();
for(int d=0;d<=11;d++){//枚举12个扩展方向
int x,y,st;
x=s.r+dx[d];//计算马按d方向跳跃后的位置
y=s.c+dy[d];
if(x>0&&y>0&&x<=100&&y<=100)
if(Step[x][y]==-1){//若（x,y)满足约束条件
Step[x][y]=s.s+1;//计算（1，1）到（x,y）的最少步数
news.r=x;
news.c=y;
news.s=Step[x][y];
q.push(news);
if(Step[x1][y1]>0&&Step[x2][y2]>0){//输出问题的解
cout<<Step[x1][y1]<<endl;
cout<<Step[x2][y2]<<endl;
return 0;
}
}
}
}
}
有帮助的话采纳一下哦！
#include <stdio.h>
int main()
{
int dx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2};
int dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};
//初始位置入队
int head=1,tail=1;
//s数组用于存放每点到各点的最少步数，que数组用于存放原点可到达的点
int s[101][101],que[10000][4]={0};
//x,y用于记录走日字或田字的坐标
int x1,y1,x2,y2;
//s数组初始化
memset(s,0xff, sizeof(s));
que[1][1]=1;
que[1][2]=1;
que[1][3]=0;
//cin>>x1>>y1>>x2>>y2;//读入黑马和白马的位置
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int d;
//BFS实现
//队列非空则扩展首节点
while(head<=tail){
//枚举12个扩展方向
for ( d = 0; d <=11 ; ++d) {
//计算马跳跃后的方向
int x=que[head][1]+dx[d];
int y=que[head][2]+dy[d];
//判断跳跃后的位置是否越界
if(x>0&&y>0){
//判断该点是否走过
if(s[x][y]==-1){
//计算起点到该点的最少步数
s[x][y]=que[head][3]+1;
//起点到该点的最少步数入队
tail++;
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;
printf("%d\n",s[x1][y1]);
printf("%d\n",s[x2][y2]);
system("pause");
return 0;
}
}
}
}
head++;
}
return 0;
}
//参考：https://blog.csdn.net/qew2017/article/details/104364561