#587. 小蝌蚪找妈妈2(CJP)

小蝌蚪找妈妈2(CJP)

背景

威海市实验高中收到了来自哈工大的一份礼物——两只黑天鹅,小蝌蚪们和青蛙妈妈们都来欣赏两只天鹅闭月羞花倾国倾城的容貌了。

题目描述

一只小蝌蚪kiki跟丢了它的妈妈,后面又有一只不明生物跟着它,现在需要你帮它找到妈妈并躲避危险。

池塘是一个n×mn×m大小的矩形,其中会有河流和山丘两种地形。小蝌蚪未长大前只能在河流区域内活动。经过kk小时后,kiki会长大,变成小青蛙,但仍只能在河流区域内活动。山丘太过陡峭,无法通过。kiki只能向前、后、左、右四个方向前行。

kiki后方的不明生物沿着kiki的路线前行,与kiki速度相同,因此kiki不能在原地静止不动。不明生物会在kiki经过的区域内设置陷阱,kiki再次进入会遇到危险,所以无法再次通过该区域。

kiki只能在池塘中行动,不能到达池塘边界上或边界外。

输入格式

n+3n+3行。

11行包含2个正整数 mmnn ,表示池塘的长与宽(不计边界宽度)。

22行至第n+1n+1行,每行mm个非负整数pp,表示通过该区域所需小时数和该区域的地形:

pp输入为00,代表该位置为山丘。

pp输入为正数,代表该位置为河流,该位置数字为通过小时数。

n+2n+2行为11个正整数 kk,代表kiki长大所需小时数。

n+3n+3行为44个正整数 x1x1y1y1x2x2y2y2 ,分别表示kiki出发位置到池塘左边界、池塘上边界的距离和青蛙妈妈位置到池塘左边界、池塘上边界的距离。 举例:m=4,n=4,x1=3,y1=2,x2=4,y2=4时

- 0 1 2 3 4 5
0 边界 边界 边界
1 0 0 0
2 kiki出发位置
3 0
4 青蛙妈妈位置
5 边界

上面显示不对时看下图

输出格式

(1)若kiki能找到妈妈且不遇到危险,则第一行输出找到妈妈的最短小时数(需计算kiki的出发位置和青蛙妈妈位置的小时数)。

第二行输出在最短时间下找到妈妈时kiki是否长大,长大输出"Yes!",没长大输出"No."。

(2)若不能找到妈妈或遇到危险(无路可走),则输出"Can Not Find."。

样例1

样例输入1

3 3
4 5 2
1 2 3
1 5 1
5
1 1 3 3

样例输出1

11
Yes!

数据规模与约定

对于 20%20\%的数据, 2mn52 ≤ m,n ≤ 5

对于另 20%20\%的数据, 0p100 0 ≤ p ≤ 1000k104 0 ≤ k ≤ 10^4

对于100% 100\%的数据,0p10100 ≤ p ≤ 10^{10}109k101110^{9} ≤ k ≤ 10^{11}2mn1002 ≤ m,n ≤ 100

保证kiki的出发位置和青蛙妈妈的位置不为山丘。