1 人解决，5 人已尝试。
1 份提交通过，共有 38 份提交。
9.9 EMB 奖励。
2417. Exploring A Cave
单点时限: 3.0 sec
内存限制: 256 MB
A spelunker explored cave, and finally he found a room with treasures. The room is rectangle with width w and depth h, and it is split into wh small squares as shown in figure 1. The height of each square may differ from others. The height of a point on a border of squares is the height of the highest square.
Unfortunately, he is so feeble that he cannot climb up to any height, and cannot jump over a hollow with any width, and cannot jump down from any height. But, he has shock-absorbing device fortunately. He can jump down from any height by using the device. However, the device costs a cost in proportion to a difference of heights when he jump down. It costs x2 when he jump down from height x to zero. It does not cost for moving flat area. He can walk freely in the level place, and it does not cost at all.
Your job is to write a program to calculate a minimum cost for him to move to a position having treasure. His first position is the center of mass of the square on the lower-left corner, that coordinate is (w , h ) = (0.5, 0.5). You should ignore the size of him and treasure.
Let us consider the first test case in the sample input for example. If he moves as shown in figure 2, he can move to the position having treasure by cost 2 because he jump down two times in 1 height difference.
输入格式
Input consists of multiple test cases. The first line of each test case contains two positive integers w and h ( w , h < 500 ). The following h lines contain w positive integers. The j-th integer in the i -th line of these lines indicates the height of the square whose upper-right point is (w , h ) = ( j ,i ). The following line contains two positive integer x (x <= w) and y ( y <= h ). These integers indicate a position of treasure is the center of mass of a square whose upper-right point is (x , y ).
Input is terminated by a case of w = h = 0, and it should not be processed.
You can assume that the height of a square does not exceed 231.
输出格式
For each test case, you should output a minimum cost for him if it is possible to him to move to a position of treasure. Otherwise, output “Impossible”.
Note for C++
Using “cin” for taking input may cause Time Limit Exceeded. For taking input, we recommend you to use standard C functions such as “scanf” instead of “cin”.
样例
Input
5 3 3 3 1 1 1 3 3 2 1 1 3 3 3 1 1 5 2 2 2 1 2 2 2 2 2 0 0
Output
2 Impossible
题目标签