《爱与愁的故事第三弹·shopping》娱乐章。
调调口味来道水题。
爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘：***（游戏名被打上了马赛克）。这个游戏类似象棋，但是只有黑白马各一匹，在点x1,y1和x2,y2上。它们得从点x1,y1和x2,y2走到1,1。这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。现在爱与愁大神想知道两匹马到1,1的最少步数，你能帮他解决这个问题么？
第1行：两个整数x1，y1
第2行：两个整数x2，y2
第1行：黑马到1,1的距离
第2行：白马到1,1的距离
12 16 18 10
8 9
100%数据：x1,y1,x2,y2<=20
依然是单调队列版子题
#include<cstdio>
#include<cstring>
int dx[12]={2,-2,2,-2,1,1,-1,-1,2,2,-2,-2};
int dy[12]={2,2,-2,-2,2,-2,2,-2,1,-1,1,-1};
int b[1001][1001],que[100001][3],a[1001][1001];
int BFS(int x,int y){
int tail=1,head=0;
que[tail][0]=x;
que[tail][1]=y;
b[x][y]=1;
do{
head++;
for (int i=0;i<12;i++){
int x1=que[head][0]+dx[i];
int y1=que[head][1]+dy[i];
if (x1>=1 && x1<=50 && y1<=50 & y1>=1 && b[x1][y1]==0){
tail++;
que[tail][0]=x1;
que[tail][1]=y1;
b[x1][y1]=1;
a[x1][y1]=a[que[head][0]][que[head][1]]+1;
}
}
}while (head<tail);
return a[1][1];
}
int main(){
int x1,y1,i,j;
scanf("%d%d",&x1,&y1);
printf("%d\n",BFS(x1,y1));
memset(b,0,sizeof(b));
memset(que,0,sizeof(que));
memset(a,0,sizeof(a));
scanf("%d%d",&x1,&y1);
printf("%d\n",BFS(x1,y1));
return 0;
}
原文：https://www.cnblogs.com/ainiyuling/p/11194454.html