水题(water)
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Background
当然,前文的几点,其实又有些片面了,真的会存在某个万能的方法,可以解决万事万物,或者是解决某个类型的题目?也许有高级的做法来解决简单的题目(也就是牛刀杀鸡),不过学无止境,方法善变,你还是需要自行寻找一切。
Description
正如前文所说,只需要简单的变形,就可以让题目变难,例如走迷宫,求最短路,很简单吧,相信大家都会做。
现在给你一个的迷宫,你每秒可以向上下左右四个方向移动1格,需要求从出发到达的最快时间。每个点都有高度。其中的是水池,你不能从水池走过,也不能呆在水池上
到了这里都很简单,我们给它添加一个条件:
- 现在开始洪水泛滥,一开始水平面的高度为0,每秒水平面高度上升一格
- 因此当与水池相邻的地块的高度小于等于水平面时,洪水将淹没这个地块,让这个地块也变成水池
那么,基于这样的前提下,最快的时间是多少呢?
Format
Input
第一行输入六个正整数
接下来行,每行个非负整数,第行第个数为
Output
出发到达的最快时间,若到达不了,输出
Samples
4 4 1 1 4 4
1 0 0 0
2 3 4 5
0 6 0 6
0 7 3 7
6
路径为:
4 4 1 1 4 4
1 0 0 0
1 2 4 5
0 6 0 6
0 7 3 7
-1
现在当你走到时,水会淹没当前位置,导致实际上不能走到,因此无法走到终点
对于的数据,
另有的数据,保证不会出现“洼地”(且直接相连的四个位置都大于)
另有的数据,
对于的数据,$n,m\leq 1000, 0\leq A_{i,j}\leq 10^5,x_a,x_b,y_a,y_b$在迷宫范围内
本题数据比较大,建议选手使用较快的读入方式