LCPC12D - Johnny Hates Climbing

Johnny has a map of the gang block which shows the heights of all buildings within the block. The plan is that a helicopter will drop Johnny on the roof of one of the buildings on the boundaries of the block during night. Then Johnny will get to the boss's building by moving to adjacent buildings, vertically or horizontally. Going up severely affects Johnny’s heart, so he can only go to a building which has the same or smaller height as the current building.

Given the gang building block map which shows the heights of all buildings in the block along with the boss building, write a program to help Johnny determine the safest path from any building on the boundary of the block to reach the boss’s building without going up. A path safety is measured by the maximum jump value between any two buildings along the path, where the jump value is the difference between the heights of the two buildings (the building he jumps from and the building he jumps to).  The safest path is the path with minimum safety value.

Input

The first line of input contains an integer T, the number of test cases. T test cases follow, the first line of each test case contains two integers (1 <= R,C <= 10) the height and the width of the building block. The second line contains two integers (1 <= BR <= R), and (1 <= BC <= C), the coordinates of the boss’s building on the map. R lines follows; each line consists of C space separated integers representing the heights of all buildings. A height H of a building satisfies (1 <= H <= 1000).

Output

For each test case, output the result using the following format:

k. S

Where k is the test case number (starting at 1), a single period (.), a single space, and S (the safety value of the safest path) or "IMPOSSIBLE" (quotes for clarity) if there is no path to the boss's building.

Sample

Input
2
3 3
2 2
1 7 3
2 6 3
3 5 4
2 2
2 1
2 7
2 6

Output
1. 1
2. 0

Added by:Gareev
Date:2012-10-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:LCPC 2012

hide comments
2020-02-17 14:21:55
dijkstra with state = (vertex, change in height)
2014-12-29 14:53:44 Kevin Sebastian
@author please check if testcases are correct as I am continuously getting WA even though I checked with multiple test cases. Also please share any tricky test cases. Submission id 13299374
2014-12-29 14:48:54 Kevin Sebastian
@Gareev I am getting a compilation error for no reason even though it is perfectly running in my system ubmission id 13299328
2013-03-09 03:12:58 hahaha
I solved it.
The program run fast.
0.00s and 308k
2012-11-14 10:40:40 :D
Boundary are all the buildings lying on first or last column or row. Result is 0.
2012-11-14 00:48:27 Ravi Kiran
WA was due to printing ':' instead of '.'
Thanks zukow for the clarification!

Last edit: 2012-11-14 21:15:06
2012-10-17 17:30:22 :D
Max(|5-4|,|4-3|,|3-2|,|2-1|) = 1
2012-10-17 16:00:34 Ehor Nechiporenko
Could you please clarify the value of the path safety.
As example for path with building heights:
5 4 3 2 1
Will it be equal to 1 or to 4?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.