Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ a
Slovak University of Technology
Pavol Jozef Saf´rik University in Koˇice
s
cz
ˇ
University of Zilina
Masaryk University
Matej Bel University in Bansk´ Bystrica
a
University of West Bohemia
CTU Open Contest 2014
Direct Visibility
visible.c, visible.cpp, Visible.java
In 2000, the contest activities sort-of culminated at the Czech Technical University. There were
another three competitions again (for the last time, probably), including the third Central Eu-
rope Regional Contest in a row. The region then moved to Warsaw and FEL++ was temporarily
suspended.
We will end our small historical excursion here and present you the fifth and last problem that
originates from our rich archives. It appeared in the 2000 Central Europe Regional Contest.
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 measure-
ments 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 electro-magnetic
fields, the transceiver power and signal quality. This equipment is packed into a huge knapsack
and the technician must move with it from one BTS to another. Unfortunately, the knapsack
has 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 neighboring BTSes such that at least one them
is always visible. For simplicity, a town is modelled as a rectangular grid of P × Q square
fields. Each field is exactly 1 meter wide. For each field, a non-negative integer Zi,j is given,
representing the height of the terrain in that place, in meters. That means the town model is
made of cubes, each of them being either solid or empty.
The technician is moving in steps (steps stands for Standard Technician's Elementary Positional
Shift). Each step is made between two neighboring square fields 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 meter up or descend at most 3 meters
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 (data are 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 segment connecting
the centers 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 meter above the surface and in the center of the appropriate square field.
Note that the IRDA beam can also go between two cubes that touch each other by their edge,
although there is no real space between them. It is because such a beam touches both of these
two cubes but does not intersect them.
Input Specification
There is a single positive integer T on the first line of input. It stands for the number of test
cases to follow. 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 Zi,j , where 1 ≤ i ≤ P , 1 ≤ j ≤ Q and 0 ≤ Zi,j ≤ 5000.
After the terrain description, there are four numbers R1, C1, R2, C2 on the last line of each test
case. These numbers represent positions of two BTSes, 1 ≤ R1, R2 ≤ P , 1 ≤ C1, C2 ≤ Q. The
first coordinate determines the row of the town, the second coordinate determines the column.
Output Specification
You are to find the shortest possible path meeting the above criteria. That is, all steps must be
done between neighboring 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!".
Output for Sample Input
Sample Input
The shortest path is 10 steps long.
4
Mission impossible!
5
5
The shortest path is 14 steps long.
8
76
5
4
The shortest path is 18 steps long.
2
22
2
2
2
22
2
2
2
22
2
2
2
22
2
2
1
15
1
5
8
2
22
2
2
2
2
2
2
22
2
2
2
2
2
2
22
2
2
2
2
2
9
99
9
9
9
9
2
2
22
2
2
2
2
2
1
25
1
5
8
2
22
2
2
2
2
2
2
22
2
2
2
2
2
2
22
2
2
2
2
2
9
99
9
9
9
9
2
2
22
2
2
2
2
2
1
55
1
6
12
5
55
51
5
5
5
5
5
5
5
5
55
51
5
5
5
5
5
5
5
5
55
59
5
5
5
5
5
5
5
5
91
55
5
5
5
5
5
5
5
5
59
55
5
5
5
5
5
5
5
5
59
55
5
5
5
5
5
5
5
6
13
12
