P2385 青铜莲花池

    • 294通过
    • 865提交
  • 题目提供者 fanhaotian
  • 评测方式 云端评测
  • 标签 USACO
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    为了让奶牛们娱乐和锻炼,农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了 M 行 N 列个方格(1 ≤ M, N ≤ 30) 。一些格子是坚固得令人惊讶的莲花,还有一些格子是岩石,其余的只是美丽、纯净、湛蓝的水。

    贝西正在练习芭蕾舞,她站在一朵莲花上,想跳到另一朵莲花上去,她只能从一朵莲花跳到另一朵莲花上,既不能跳到水里,也不能跳到岩石上。

    贝西的舞步很像象棋中的马步:每次总是先横向移动 M1 (1 ≤ M1 ≤ 30)格,再纵向移动 M2 (1 ≤ M2 ≤ 30, M1≠M2)格,或先纵向移动 M1 格,再横向移动 M2 格。最多时,贝西会有八个移动方向可供选择。

    给定池塘的布局和贝西的跳跃长度,请计算贝西从起点出发,到达目的地的最小步数,我们保证输入数据中的目的地一定是可达的。

    输入输出格式

    输入格式:

    第一行:四个用空格分开的整数:M,N,M1 和 M2

    第二行到 M + 1 行:第 i + 1 行有 N 个用空格分开的整数,描述了池塘第

    i 行的状态:0 为水,1 为莲花,2 为岩石,3 为贝西所在的起点,4 为贝西想去

    的终点。

    输出格式:

    第一行:从起点到终点的最少步数。

    输入输出样例

    输入样例#1: 复制
    4 5 1 2
    1 0 1 0 1
    3 0 2 0 4
    0 1 2 0 0
    0 0 0 1 0
    输出样例#1: 复制
    2
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。