塔防
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
gsy 最近在玩一个塔防游戏，但是这次她控制的是迷宫中的怪兽而非防御塔建造者
游戏的地图是一个 n * m 的矩阵，起点在 (1,1) ，终点在 (n,m) ，gsy 每次可以选择上下左右四个方向移动 1 步
这个地图上有很多的防御塔，gsy 每次移动结束后，所有防御塔都会对它进行一次攻击
在这个游戏中，她离某个防御塔越远，这个防御塔能对她造成的伤害就越高
设 gsy 某次移动到达位置 (x,y) ，某个防御塔位于坐标 (X,Y) ，那么这个防御塔在这一次攻击会对 gsy 造成 |X-x| + |Y-y| 点伤害
为了通关，gsy 又给自己开了金手指，可以使得在这一轮游戏中，防御塔的攻击不会造成伤害，而是造成等值的血量回复
现在 gsy 想找到一条从起点到终点的路径，并且自己在途中受到的来所有自防御塔单次攻击的最小值尽可能大
P.S. 在这个游戏中，gsy 可以走到防御塔的位置上
输入格式
第一行两个数 n,m 。
接下来 n 行，每行 m 个数，如果该数为 0 ，则表示该位置是空地，否则则表示这个位置有防御塔。
数据保证至少存在一个防御塔。
输出格式
一个数表示答案
样例
3 4
0 1 1 0
0 0 0 0
1 1 1 01提示
对于 40% 的数据 n,m <= 10
对于 80% 的数据 n,m <= 100
对于 100% 的数据 n,m <= 1000
20230116寒假提高组level-5集训
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 6
- 开始于
- 2023-1-16 10:00
- 结束于
- 2023-1-26 10:00
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 16
