学步园

【问题描述】
在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（100*100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点可能的最少步数。
【输入样例】
12 16
18 10
【输出样例】
8

9

问题分析

1、确定出发点
从（x,y）出发通过一次广度优先搜索，可以找到从(x,y)至棋盘上所有可达点的最少步数。而问题中要求的是黑马所在的（x1，y1）和白马所在（x2，y2）到达 (1,1) 目标点的最少步数。虽然两条路径的起点不一样，但是它们的终点却是一样的。如果我们将终点(1,1)作为起点，这样只需要一次广度优先搜索便可以得到（x1，y1）和（x2，y2）到达(1,1)的最少步数。
2、数据结构
需要3个队列来分别存储扩展点的行坐标、列坐标和改点到目标点的最小步数，初始时，队列中只有一个元素为(1,1)，最少步数为0。
dis数组­—记录(1,1)到每点所需要的最少步数。显然，问题的答案是dis[x1][y1]和dis[x2][y2]。初始时，dis[1][1]为0，除此之外的所有元素值设为-1。
dx、dy——移动后的位置增量数组。马有12种不同的扩展方向：
马走“日”：(x-2,y-1)(x-1,y-2)(x-2,y+1)(x-1,y+2)(x+2,y-1)(x+1,y-2)(x+2,y+1)(x+1,y+2)
马走“田”：(x-2,y-2)(x-2,y+2)(x+2,y-2)(x+2,y+2)
我们将i方向上的位置增量存入常量数组dx[i]、dy[i]中（0≤i≤11）
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};

c++代码：

#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const 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 x1,y1,x2,y2;
int dis[110][110];
void init();
int work();	
int main()
{	
	init();
	work();
	return 0;
}
void init()
{
	memset(dis,0xff,sizeof(dis));//0xff是16进制，这样可把符号类型变量赋为-1 
	cin>>x1>>y1>>x2>>y2;
	dis[1][1]=0;
}
int work()
{
	queue<int> x,y,step;//x为存储行的队列，y存储列，step存储改点到（1,1）最少步数 
	x.push(1);
	y.push(1);
	step.push(0);
	while(!x.empty())//当队列非空时 
	{
		for(int i=0;i<12;++i)//对队首点向12个可能点进行扩展 
		{
			int next_x=x.front()+dx[i];
			int next_y=y.front()+dy[i];
			if(next_x>0 && next_y>0 && dis[next_x][next_y]==-1)//如果改点没访问过 
			{
				dis[next_x][next_y]=step.front()+1;//改点的最小步数是队首的距离加一 
				x.push(next_x);//改点进队列 
				y.push(next_y);
				step.push(dis[next_x][next_y]);
				if(dis[x1][y1]>0 && dis[x2][y2]>0)
				{
					cout<<dis[x1][y1]<<endl;
					cout<<dis[x2][y2]<<endl;
					return 0;
				}
			}
		}
		x.pop();//队首扩展完毕，将其出队 
		y.pop();
		step.pop();
	}	
}