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

问题描述：

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

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

【输入格式】

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

【输出格式】

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

【样例输入】

 4 0 2 1 2

【样例输出】

 3

【样例说明】

【样例输入】

 4 2 2 2 3

【样例输出】

 2

【样例说明】

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

【评测用例规模与约定】

 对于 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]=0
    ls=[]
    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+1
                p.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的棋盘，节点是棋盘上的每个位置，边是骑士可以走的合法移动。

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

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

整体逻辑是通过BFS算法搜索从起点到终点的最短路径。

“ 我们的科学永远只是找到近似真理。”——《爱因斯坦》