1330：【例8.3】最少步数

1330：【例8.3】最少步数

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 13863     通过数: 7606

【题目描述】

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

【输入】

A、B两点的坐标。

【输出】

最少步数。

【输入样例】

12 16
18 10

【输出样例】

8
9

【算法分析】

由于A、B两点是随机输入的，因此无法找到计算最少步数的数学规律，只能通过广度优先搜索的办法求解。

（1）确定出发点

从（n，m）出发通过一次广度优先搜索，可以找到从（n，m）至棋盘上所有可达点的最少步数。而问题中要求的是黑马所在的（x1，yy1）和白马所在（x2，y2）到达（1,1）目标点的最少步数。虽然两条路径的起点不一样，但是它们的终点却是一样的。如果我们将终点（1,1）作为起点，这样只需要一次广度优先搜索便可以得到（x1，yy1）和（x2，y2）到达（1,1）的最少步数。

（2）数据结构

设queue——队列，存储从（1,1）可达的点（queue[k][1..2]）以及到达该点所需要的最少步数（queue[k][3]）（0k192+1）。队列的首指针为head，尾指针为tail。初始时，queue中只有一个元素为（1,1），最少步数为0。

a——记录（1,1）到每点所需要的最少步数。显然，问题的答案是a[x1][yy1]和a[x2][y2]。初始时，a[1][1]为0，除此之外的所有元素值设为-1。

dx、dy——移动后的位置增量数组。马有12种不同的扩展方向：

马走“日”：

（n-2，m-1）（n-1，m-2）（n-2，m+1）（n-1，m+2）（n+2，m-1）（n+1，m-2）（n+2，m+1）（n+1，m+2）

马走“田”：

（n-2，m-2）（n-2，m+2）（n+2，m-2）（n+2，m+2）

我们将i方向上的位置增量存入常量数组dx[i]、dy[i]中（0i11）：

int dx[12]={-1,-1,-1,1,2,2,2,2,1,-1,-2,-2},dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};

（3）约束条件

（1）不能越出界外。由于马的所有可能的落脚点a均在a的范围内，因此一旦马越出界外，就将其a值赋为0，表示“已经扩展过，且（1,1）到达其最少需要0步”。这看上去是荒谬的，但可以简单而有效地避免马再次落入这些界外点。

（2）该点在以前的扩展中没有到达过。如果曾经到达过，则根据广度优先搜索的原理，先前到达该点所需的步数一定小于当前步数，因此完全没有必要再扩展下去。

由此得出，马的跳后位置（n，m）是否可以入队的约束条件是a[n][m]0。

（4）算法流程

【AC代码】

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<string>
#include<vector>
using namespace std;
const int N=1e3+10;
inline int fread()
{
	char ch=getchar();
	int n=0,m=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-')m=-1;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
	return n*m;
}
int dx[12]={-1,-1,-1,1,2,2,2,2,1,-1,-2,-2},dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1},a[N][N],q[10000][4],x1,yy1,x2,y2,head=1,tail=1;//初始位置入队
signed main()
{
	memset(a,0xff,sizeof a),q[1][1]=q[1][2]=1,q[1][3]=0,x1=fread(),yy1=fread(),x2=fread(),y2=fread();//a数组的初始化，读入黑马和白马的出发位置
	while(head<=tail)
	{
		for(int i=0;i<12;i++)//枚举12个扩展方向
		{
			int n=q[head][1]+dx[i],m=q[head][2]+dy[i];//计算马按i方向跳跃后的位置
			if(n>0 and m>0)
				if(a[n][m]==-1)//若（n，m）满足约束条件
				{
					a[n][m]=q[head][3]+1,tail++,q[tail][1]=n,q[tail][2]=m,q[tail][3]=a[n][m];//计算（1,1）到（n，m）的最少步数，（1,1）至（n，m）的最少步数入队
					if(a[x1][yy1]>0 and a[x2][y2]>0)//输出问题的解
					{
						cout<<a[x1][yy1]<<"\n";
						cout<<a[x2][y2]<<"\n";
						return 0;
					}
				}
		}
		head++;
	} 
	return 0;
}

我喜欢用数组模拟队列（还不是因为不想记队列的操作函数） 。