首页 > 代码库 > LYK 快跑!(run)
LYK 快跑!(run)
LYK 快跑!(run)
Time Limit:5000ms Memory Limit:64MB
【题目描述】
LYK 陷进了一个迷宫! 这个迷宫是网格图形状的。 LYK 一开始在(1,1)位置, 出口在(n,m)。而且这个迷宫里有很多怪兽,若第 a 行第 b 列有一个怪兽,且此时 LYK 处于第 c 行 d 列,此时这个怪兽对它的威胁程度为|a-c|+|b-d|。LYK 想找到一条路径,使得它能从(1,1)到达(n,m),且在途中对它威胁程度最小的怪兽的威胁程度尽可能大。当然若起点或者终点处有怪兽时,无论路径长什么样,威胁程度最小的怪兽始终=0。
【输入格式】(run.in)
第一行两个数 n,m。
接下来 n 行,每行 m 个数,如果该数为 0,则表示该位置没有怪兽,否则存在怪兽。
数据保证至少存在一个怪兽。
【输入格式】(run.out)
一个数表示答案。
【输入样例】
3 4
0 1 1 0
0 0 0 0
1 1 1 0
【输出样例】
1
【数据范围】
对于 20%的数据 n=1。
对于 40%的数据 n<=2。
对于 60%的数据 n,m<=10。
对于 80%的数据 n,m<=100。
对于 90%的数据 n,m<=1000。
对于另外 10%的数据 n,m<=1000 且怪兽数量<=100。
【题目分析】
LYK 快跑!(run)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。