第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法详解

本文主要是介绍第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

博客主页：誓则盟约

系列专栏：IT竞赛专栏

关注博主，后期持续更新系列文章

如果有错误感谢请大家批评指出，及时修改

感谢大家点赞👍收藏⭐评论✍

问题描述：

小蓝有一个大小为 N × N 的棋盘（棋子可以走的位置有 (N + 1) × (N + 1) 个），棋盘上只有两个棋子：一个马和一个象，他们的行动规则是：马走日，马可以走到一个日字形状的对角；象飞田，象可以走到一个田字形状的对角，即斜着走两格（注意无需遵守象棋中的蹩马腿、塞象眼的规则）。在下图所示的大小为 4 × 4 的棋盘上，展示了两种棋子具体的行进方式：

在任意一方先手、每一方都可以连续走任意步的情况下，请问有没有可能出现一方吃掉另一方的局面，如果有，请输出最少需要经过几步可以达到这个局面，否则输出 −1 。注意：棋子不能走出棋盘。

【输入格式】

输入一行包括五个整数 N, x1, y1, x2, y2 ，相邻整数之间使用一个空格分隔，表示棋盘大小、马的初始位置 (x1, y1) 以及象的初始位置 (x2, y2) 。

【输出格式】

输出一行包含一个整数表示答案。如果答案不存在输出 −1 。

【样例输入】

4 0 2 1 2

【样例输出】

【样例说明】

【样例输入】

4 2 2 2 3

【样例输出】

【样例说明】

各走一步可能出现一方吃掉另一方的局面。

【评测用例规模与约定】

对于 50% 的评测用例，1 ≤ N ≤ 10 ；对于所有评测用例，1 ≤ N ≤ 50 ，0 ≤ x1, y1, x2, y2 ≤ N 。

分析问题：

首先，这个问题很明显是在考察BFS的运用，马和象的可移动规则给了，我们只需要给这两个规则转化为两个dirs，遍历其中一个dirs（这里我们以象为终点，首先遍历象的方向）将其可能到达的坐标加入到列表ls里面存储起来，然后去遍历另一个（马）可能走到的坐标，如果这个坐标在ls里面，那说明他们可以相遇，直接返回当前步数即可（因为我们是BFS广度优先，此时的步数一定是最少的步数，可以直接返回）。如果没有存在ls里，则继续遍历，直到遍历完所有可以走的坐标为止，此时则说明二者不能相遇，则返回-1即可。这是当前的大致思路，主要还是看代码实现，这道题用了两个BFS，严格考察对BFS和队列的理解和运用能力。

代码实现：


n,x1,y1,x2,y2=map(int,input().split())def BFSM(n,x1,y1,x2,y2):dirs={lambda x,y:(x+1,y+2),lambda x,y:(x+2,y+1),lambda x,y:(x+2,y-1),lambda x,y:(x+1,y-2),lambda x,y:(x-1,y-2),lambda x,y:(x-2,y-1),lambda x,y:(x-2,y+1),lambda x,y:(x-1,y+2)}dirs2={lambda x,y:(x-2,y+2),lambda x,y:(x+2,y+2),lambda x,y:(x+2,y-2),lambda x,y:(x-2,y-2),}seen=set()st=(x1,y1)ed=(x2,y2)seen.add(st)q=[(st,0)]p=[(ed,0)]seen_1={}seen_1[ed]=0ls=[]while p:now_1,step_1=p.pop(0)for dir in dirs2:new_1=dir(now_1[0],now_1[1])if 0<=new_1[0]<=n+1 and 0<=new_1[1]<=n+1 and new_1 not in seen_1.keys():seen_1[new_1]=step_1+1p.append([new_1,step_1+1])while q:now_node,step=q.pop(0)if now_node in seen_1.keys():kk=step+seen_1[now_node]ls.append(kk)for dir in dirs:new_node=dir(now_node[0],now_node[1])if 0<=new_node[0]<=n+1 and 0<=new_node[1]<=n+1 and new_node not in seen:seen.add(new_node)q.append([new_node,step+1])if ls:return min(ls)else: return -1
print(BFSM(n,x1,y1,x2,y2))

总结：

这里的n指的是棋盘的边长，而x1和y1是起点的坐标，x2和y2是终点的坐标。函数BFSM使用了广度优先搜索（Breadth-First Search, BFS）算法，它是一种在图论中用于遍历图或树的数据结构的算法。在这个问题中，图是n乘n的棋盘，节点是棋盘上的每个位置，边是骑士可以走的合法移动。

下面是代码分步功能的详细解释：

dirs是一个包含八个函数的集合，每个函数代表骑士可以走的八种合法移动的方向。例如，lambda x,y:(x+1,y+2)表示骑士可以从(x, y)移动到(x+1, y+2)。
dirs2是一个包含四种函数的集合，每个函数代表终点(x2, y2)可以到达的四个特殊位置。这些位置是终点位置的四个对角线方向上两个单位距离的位置。
seen是一个集合，用于记录已经访问过的节点。
q是广度优先搜索的队列，用于存储待访问的节点及其到起点的距离。
p是另一个队列，用于存储从终点开始的访问过程，目的是找到从终点到起点的路径。
seen_1是一个字典，用于记录从终点开始访问过程中每个节点到终点的距离。
函数BFSM首先初始化seen集合和q队列，然后开始广度优先搜索。
在广度优先搜索的过程中，每次检查当前节点now_node是否在seen_1中，如果是，则计算从起点到当前节点的距离加上从当前节点到终点的距离，并将这个总距离添加到ls列表中。
然后，对于当前节点的每个合法移动方向，检查新位置是否在棋盘。