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.
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).
For each test case, output the result using the following format:
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.
1 7 3
2 6 3
3 5 4
@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
@Gareev I am getting a compilation error for no reason even though it is perfectly running in my system ubmission id 13299328
Last edit: 2013-06-16 17:50:30
I solved it.
Boundary are all the buildings lying on first or last column or row. Result is 0.
WA was due to printing ':' instead of '.'
Max(|5-4|,|4-3|,|3-2|,|2-1|) = 1
Could you please clarify the value of the path safety.