P1747 好奇怪的游戏

好奇怪的游戏

题目背景

《爱与愁的故事第三弹·shopping》娱乐章。

调调口味来道水题。

题目描述

爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘：***（游戏名被打上了马赛克）。这个游戏类似象棋，但是只有黑白马各一匹，在点 $x_1,y_1$ 和 $x_2,y_2$ 上。它们得从点 $x_1,y_1$ 和 $x_2,y_2$ 走到 $(1,1)$。这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。现在爱与愁大神想知道两匹马到 $(1,1)$ 的最少步数，你能帮他解决这个问题么？

注意不能走到 $x$ 或 $y$ 坐标 $\le 0$ 的位置。

输入格式

第一行两个整数 $x_1,y_1$。

第二行两个整数 $x_2,y_2$。

输出格式

第一行一个整数，表示黑马到 $(1,1)$ 的步数。

第二行一个整数，表示白马到 $(1,1)$ 的步数。

样例 #1

样例输入 #1

12 16
18 10

样例输出 #1

8 
9

提示

数据范围及约定

对于 $100\%$ 数据，$1\le x_1,y_1,x_2,y_2\le 20$。

#include<iostream>
#include<cstring>
#include<map>
using namespace std;
typedef pair<int ,int> PII;
#define x first
#define y second
const int N=30;
int d[N][N];
bool st[N][N];
int dx[]={-2,-2,-1,-1,1,1,2,2,-2,-2,2,2};
int dy[]={-1,1,2,-2,2,-2,-1,1,-2,2,-2,2};
PII q[N*N];

void bfs(int x1,int y1){
	memset(st,false,sizeof st);
	memset(d,-1,sizeof d);
	int hh=0,tt=-1;
	q[++tt]={x1,y1};
	st[x1][y1]=true;
	d[x1][y1]=0;
	
	while(hh<=tt){
		PII t=q[hh++];
		
		for(int i=0;i<12;i++){
			int x2=t.x+dx[i];
			int y2=t.y+dy[i];
			
			if(x2<1||x2>x1||y2<1||y2>y1)continue;
			if(st[x2][y2])continue;
			
			q[++tt]={x2,y2};
			st[x2][y2]=true;
			d[x2][y2]=d[t.x][t.y]+1;
			if(x2==1&&y2==1)return;
		}
		
	}
	
}

int main(){
	int x1,y1,x2,y2;
	cin>>x1>>y1>>x2>>y2;
	
	bfs(x1,y1);
	cout<<d[1][1]<<'\n';
	bfs(x2,y2);
	cout<<d[1][1]<<'\n';
}