DIRVS  Direct Visibility
Building the GSM network is a very expensive and complex task. Moreover, after the Base Transceiver Stations (BTS) are built and working, we need to perform many various measurements to determine the state of the network, and propose effective improvements to be made.
The ACM technicians have a special equipment for measuring the strength of electromagnetic fields, the transceivers' power and quality of the signal. This equipment is packed into a huge knapsack and the technician must move with it from one BTS to another. Unfortunately, the knapsack have not enough memory for storing all of the measured values. It has a small cache only, that can store values for several seconds. Then the values must be transmitted to the BTS by an infrared connection (IRDA). The IRDA needs direct visibility between the technician and the BTS.
Your task is to find the path between two neighbouring BTSes such that at least one of those BTSes is always visible.
Input
There is a single positive integer T on the first line of input (equal to about 500). It stands for the number of test cases to follow. Each test case consists of a town description. For simplicity, a town is modelled as a rectangular grid of P x Q square fields. Each field is exactly 1 metre wide. For each field, a nonnegative integer Z_{i,j} is given, representing the height of the terrain in that place, in metres. That means the town model is made of cubes, each of them being either solid or empty. There are no "half solid" cubes.
The first line of each test case contains two integer numbers P and Q, separated by a single space, 1 <= P,Q <= 200. Then there are P lines each containing Q integer numbers separated by a space. These numbers are Z_{i,j}, where 1 <= i <= P, 1 <= j <= Q and 0 <= Z_{i,j} <= 5000. After the terrain description, there are four numbers R_{1}, C_{1}, R_{2}, C_{2} on the last line of each test case. These numbers represent position of two BTSes, 1 <= R_{1},R_{2} <= P, 1 <= C_{1},C_{2} <= Q. The first coordinate (R) determines the row of the town, the second coordinate determines the column.
The technician is moving in steps (steps stands for Standard Technician's Elementary Positional Shift). Each step is made between two neighbouring square fields. That means the step is always in North, South, West or East direction. It is not possible to move diagonally. The step between two fields A and B (step from A to B) is allowed only if the height of the terrain in the field B is not very different from the height in the field A. The technician can climb at most 1 metre up or descend at most 3 metres down in a single step.
At the end of each step, at least one of the two BTSes must be visible. However, there can be some point "in the middle of the step" where no BTS is visible. This is OK and the data is handled by the cache. The BTS is considered visible, if there is a direct visibility between the unit cube just above the terrain on the BTSes coordinates and the cube just above the terrain on the square field, where the technician is. Direct visibility between two cubes means that the line connecting the centres of the two cubes does not intersect any solid cube. However, the line can touch any number of solid cubes. In other words, consider both the BTS and the technician being points exactly half metre above the surface and in the centre of the appropriate square field.
Note that the IRDA beam can go between two cubes that touch each other by their edge, although there is no space between them. It is because such a beam touches both of these two cubes but does not intersect any of them. See the last test case of the sample input for an example of such a situation.
Output
You are to find the shortest possible path from BTS (R_{1}, C_{1}) to BTS (R_{2}, C_{2}), meeting the above criteria. All steps must be done between neighbouring fields, the terrain must not elevate or descend too much, and at the end of each step, at least one BTS must be visible.
For each test case, print one line containing the sentence The shortest path is M steps long., where M is the number of steps that must be made. If there is no such path, output the sentence Mission impossible!.
Example
Sample Input:
4 5 5 8 7 6 5 4 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 5 1 5 8 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 9 9 9 9 9 9 9 2 2 2 2 2 2 2 2 2 1 2 5 1 5 8 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 9 9 9 9 9 9 9 2 2 2 2 2 2 2 2 2 1 5 5 1 6 12 5 5 5 5 1 5 5 5 5 5 5 5 5 5 5 5 1 5 5 5 5 5 5 5 5 5 5 5 9 5 5 5 5 5 5 5 5 9 1 5 5 5 5 5 5 5 5 5 5 5 9 5 5 5 5 5 5 5 5 5 5 5 9 5 5 5 5 5 5 5 5 5 6 1 3 12
Sample Output:
The shortest path is 10 steps long. Mission impossible! The shortest path is 14 steps long. The shortest path is 18 steps long.
hide comments
kumar gaurav:
20151006 10:53:34
can we use cache for only one movement?


Rafail Loizou:
20150325 16:19:54
still can not figure out how to test visibility


Mayank Raj:
20130901 21:21:57
Dijkshtra getting timed out in java :'(


ABHISHEK:
20130526 21:04:27
how to check the condition if technician is directly visible from any of the two BTS? 

tantrum:
20130522 15:29:09
will bfs work for this?? 

ahmed abd alrhman mohamed:
20130131 03:20:37
yes i do it


Giovanni Botta:
20130110 20:20:41
How about Dijkstra's algorithm?


Daniel Polaczanski:
20110604 14:40:24
Any hint to solve this problem?

Added by:  adrian 
Date:  20040508 
Time limit:  13s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  ACM Central European Programming Contest, Prague 2000 