Your friend is developing scenarios for quest-type computer games and often
turns to you to ask about the correctness of his ideas. He has done it again just
now.
The labyrinth is a grid of square cells. The cells are arranged in M lines from
North to South and N columns from West to East. The coordinates of the North-
Western cell of the grid are (1, 1); the coordinates of the South-Eastern cell are
(N, M). From the outside, the labyrinth is surrounded by non-passable external
wall. Inside the labyrinth, any cell can be either empty or contain a section of an
internal wall. Among the empty cells, K are prepared for laying mines. When a
mine explodes in one of those cells, it destroys the internal walls in the horizontally
and vertically neighboring cells, making the cells empty.
The player’s character enters the labyrinth through some empty cell A and has
to exit it through an empty cell B, distinct from the cell A. He can move only though
empty cells, stepping from a cell to a neighboring one horizontally or vertically.
Stepping from a cell to its neighbor is a move.
The character has one mine that he can (but does not have to) explode it in
one of the prepared cells. To do this, the character has to enter the cell, plant the
mine, move outside the explosion zone, and then remotely explode the mine. If the
mine is planted in the cell (x0, y0), then any cell (x1, y1) is outside the explosion
zone if at least one of the following holds:
On the figure below, if the mine explodes in the cell marked with 1, the cells
marked with 2 are safe (and the player can get there to hide in during the
explosion). The cells with surviving internal walls have gray background; the cells
with destroyed internal walls have black background.
Your task is to find the shortest (with the minimal
number of moves) route from the cell A to the cell B.
Note that the count must also include any moves
needed to get to a safe cell before and to return to the
location of the mine after the explosion, but planting the mine and exploding it are not counted as moves!
The first line of each testcase contains the integers M, N,
K (1 ≤ M, N ≤ 100, M•N > 1, 0 ≤ K ≤ 10). The second and third lines contain the coordinates of the cells A and B. Each of the following M lines contains exactly N characters, describing the labyrinth in the order from North to South. A
star (*) denotes a cell filled with an internal wall, a point (.) an empty cell, and the ’at’ sign (@) a cell prepared for planting a mine.
for each testcase should contain the
minimal number of moves needed to reach the cell B. If this is impossible, output
the value 0.
5 7 2 1 5 7 1 ***.**. @..***. **...@* ...**** .****** 5 7 2 1 5 7 1 ***.**. @..**.. **....* **...** @******
18 0
Migrated from old NTUJ.
icpc2008, neerc west
No. | Testdata Range | Score |
---|