#P12270. [蓝桥杯 2024 国 Python B] 马与象

    ID: 13921 远端评测题 3000ms 512MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>搜索2024广度优先搜索 BFS蓝桥杯国赛

[蓝桥杯 2024 国 Python B] 马与象

题目描述

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

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

输入格式

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

输出格式

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

4 0 2 1 2
3
4 2 2 2 3
2

提示

样例说明 1

样例说明 2

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

评测用例规模与约定

  • 对于 50%50\% 的评测用例,1N101 \leq N \leq 10
  • 对于所有评测用例,1N501 \leq N \leq 500x1,y1,x2,y2N0 \leq x_1, y_1, x_2, y_2 \leq N