Bob and Alice’s Meet
Now , Bob and Alice fasten the last chance on network communication to confirm the place they will meet at in the next days. The city they lived , has many roads and hotels. Of course, they can’t talk just on the roads, and they also can’t enter any buildings except hotels. So they decide to meet in a certain hotel in their city. As they know,the city’s building pattern is very regular like a rectangle with many griddings in it. And all hotels and houses are built in lines and columns, so are roads. So they can only walk straightly by lines or columns. While it is a mountainly city, every buliding may has a different height above sea level.If you walk form a hotel with a height x at an initial speed v0 to a hotel with a height y, then the speed on this road is surposed to be v0 × 2(x-y) . We already know that Bob lives in the city’s left-up corner,and Alice lives in the right-down corner. The buliding in the grid among their houses are all hotels. and the length of the road between two neighbor( four directions connected) hotel is alway a same value L, and they set up at their own initial speed at the same time.
Now , they want to pick a path which will take them a fastest time to meet each other. Pitfully for them ,can you help them to commpute the minmum time to meet ? You should always remember that ,they only meet at a certain hotel ,so maybe one of them will reach a hotel and don’t walk again to wait the other one to arrive.
Line 1 : Four space-separated integers: N, Vb, Va, L.
N is the size of the rectangle of Bob and Alice’s city. Va is Alice’s initial speed, while Vb is Bob’s initial speed. L is the length between two neighbor hotels .
Line 2 ~ Line N + 1 : every line has N space-separated integers,each one represents a hotel’s height.
N = 0 indicates the end of input and should not be processed.
3 1 1 1 1 2 3 3 2 1 1 2 1 0 0 0 0