spoj#LCPC12D. Johnny Hates Climbing

Johnny Hates Climbing

Description

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 Format

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 Format

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

Sample Output

2

3 3

2 2

1 7 3

2 6 3

3 5 4

2 2

2 1

2 7

2 6

1. 1

2. 0