博客主页:誓则盟约

系列专栏: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

【样例输出】

  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指的是棋盘的边长,而x1y1是起点的坐标,x2y2是终点的坐标。函数BFSM使用了广度优先搜索(Breadth-First Search, BFS)算法,它是一种在图论中用于遍历图或树的数据结构的算法。在这个问题中,图是nn的棋盘,节点是棋盘上的每个位置,边是骑士可以走的合法移动。

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

  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算法搜索从起点到终点的最短路径。


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

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

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部