青铜莲花池
测试数据来自 wjszez/2084
【问题描述】
为了让奶牛们娱乐和锻炼,农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了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 为贝西想去的终点。
【输出格式】
第一行:从起点到终点的最少步数
【输入样例】
bronlily.in
4 5 1 2
1 0 1 0 1
3 0 2 0 4
0 1 2 0 0
0 0 0 1 0
【输出样例】
2
样例解释:贝西从第二行的最左边出发,目标是第二行的最右边。贝西先跳到第一行第三列的莲花上,再跳到终点,需要两步。
信息
- ID
- 2492
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者