K11544 最少步数

题目描述

在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。

小科就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试。

在一个（100×100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。

现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点可能的最少步数。

输入格式

两行

第一行，两个整数，代表A的坐标

第二行，两个整数，代表B的坐标

输出格式

两行

第一行，A点到(1,1)点可能的最少步数

第二行，B点到(1,1)点可能的最少步数

输入输出样列

输入样例1：                                                            输出样例1：

12 16                                        8
18 10                                        9

AC代码：

#include
using namespace std;
const int N=105,dlt[12][2]={{-2,-2},{-2,-1},{-2,1},{-2,2},{-1,2},{1,2},{2,2},{2,1},{2,-1},{2,-2},{1,-2},{-1,-2}};
struct Vex{
	int x,y;
}a,b,dst;
int dis[N][N];
inline bool judge(Vex v){
	return v.x>=1&&v.x<=100&&v.y>=1&&v.y<=100;
}
void bfs(Vex u){
	dis[u.x][u.y]=1;
	queue  q;
	q.push(u);
	while(!q.empty()){
		if(dis[a.x][a.y]&&dis[b.x][b.y]) return;
		u=q.front(); q.pop();
		for(int k=0;k<12;k++){
			Vex v;
			v.x=u.x+dlt[k][0],v.y=u.y+dlt[k][1];
			if(judge(v)&&!dis[v.x][v.y]){
				dis[v.x][v.y]=dis[u.x][u.y]+1;
				q.push(v);
			} 
		}
	}
}
int main(){
	cin>>a.x>>a.y>>b.x>>b.y;
	dst.x=dst.y=1;
	bfs(dst);
	cout<