【题2】最少步数

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

2、 输出： 89 题解 由于 A、B两点是随机输入的，因此无法找到计算最少步数的数学规律，只能通过广度优先搜索的办法求解。 1、确定出发点 从（x,y）出发通过一次广度优先搜索，可以找到从(x,y)至棋盘上所有可达点的最少步数。而问题中要求的是黑马所在的（x 2 / 5 1，y 1）和白马所在（x 2，y 2）到达(1,1)目标点的最少步数。虽然两条路径的起点不一样，但是它们的终点却是一样的。如果我们将终点(1,1)作为起点，这样只需要一次广度优先搜索便可以得到（x 1，y 1）和（x 2，y 2）到达(1,1)的最少步数。 2、数据结构设que队列，存储从(1,1)可达的点（quek, 1.2

3、）以及到达该点所需要的最少步数（quek,3）（0k192 +1）。队列的首指针为closed，尾指针为open。初始时，que中只有一个元素为(1,1)，最少步数为 0。 S记录(1,1)到每点所需要的最少步数。显然，问题的答案是sx 1,y 2和sx 2,y 2。初始时，s1,1为0，除此之外的所有元素值设为- 1。为了使得马从棋盘内任意位置扩展出的坐标均在s的范围内，我们将s数组的范围扩大至s- 3 / 5 1.21,- 1.21。 dx、dy移动后的位置增量数组。马有12种不同的扩展方向： 马走“日”： (x-2,y-1)(x-1,y-2)(x-2,y+1)(x-1,y+2)(x+2,

4、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方向上的位置增量存入常量数组dxi、dyi中（1i12） const dx： array 1.12 of integer=(-2,-2,-1,1,2,2,2,2,1,-1,-2,-2); dy： array 1.12 of integer=(-1,-2,-2,-2,-2,-1,1,2,2,2,2,1); 3、约束条件 不能越出界外。由于马的所有可能的落脚点s均在s的范围内，因此一旦马越出界外，就将其s值赋为0，表示“已经扩展过，且(1,1

5、)到达其最少需要0步”。这看上去是荒谬的，但可以简单而有效地避免马再次落入这些界外点。 该点在以前的扩展中没有到达过。如果曾经到达过，则根据广度优先搜索的原理，先前到达该点所需的步数一定小于当前步数，因此完全没有必要再扩展下去。 由此得出，马的跳后位置（x,y）是否可以入队的约束条件是sx,y<0 4 / 5 4、算法流程 fillchar(s,sizeof(s),0); s1,10; s数组的初始化for x11 to 19 do for y11 to 19 do sx1,y1-1; fillchar(que,sizeof(que),0); 队列初始化open1;closed0; 初始

6、位置入队que1,11;que1,21; read(x1,y1,x2,y2); 读入黑马和白马的出发位置while closed<open do 若队列非空，则扩展队首结点begin inc(closed); for d1 to 12 do 枚举8个扩展方向begin xqueclosed,1+dxd; 计算马按d方向跳跃后的位置yqueclosed,2+dyd; if sx,y<0 then 若（x,y）满足约束条件begin sx,yqueclosed,3+1; 计算(1,1)到(x,y)的最少步数inc(open); （x,y）和（1,1）至（x,y）的最少步数入队queopen,1x; queopen,2y; queopen,