20223번 - Kangaroo Commotion 다국어

문제

Bushfires are threatening your habitat! Being a kangaroo, you must inform the other kangaroos in your troop as fast as possible and flee to a safe area.

You are currently standing still, and you will jump to the other kangaroos' locations. You will visit the other kangaroos in a specific order so that all of them have sufficient time to escape. After visiting all other kangaroos you must continue jumping to the safe area, where you should come to a stop.

With each jump you move a (possibly negative) integer distance north and/or east. Because of your limited muscle power, you are only able to accelerate or decelerate at most 1ドル$ in each direction each jump. Formally, if jump $i$ moves you $v_{x,i}$ to the north and $v_{y, i}$ to the east, the next jump $i+1$ must satisfy $|v_{x, i+1} - v_{x, i}| \leq 1$ and $|v_{y, i+1} - v_{y, i}| \leq 1$.

Find the minimal number of jumps needed to go from your current position to the safe area via all other kangaroos, without leaving the grid. It is very important to come to a full stop at the end, so the last jump must both start and end at the safe area.

The first sample is shown in figure K.1.

Figure K.1: Visualisation of Sample 1 showing one possible way to get to the safe area using 9ドル$ jumps.

입력

The input consists of:

• A line containing three integers $r,ドル $c$ (1ドル\leq r, c \leq 50$), the number of rows and columns of the grid, and $k$ (1ドル\leq k\leq 5$), the number of other kangaroos you need to warn.
• $r$ lines each consisting of $c$ characters. A "." indicates an open space and a "#" indicates a bush where you can't jump. Your start position is indicated by a "0" and the characters "1ドル$" to $k$ indicate the positions of the other kangaroos you need to warn in this order. The position indicated by $k+1$ indicates the safe area where you should come to a stop.

출력

If it is possible to reach the safe area, then output the minimal number of steps needed to reach the safe area. Otherwise, output "impossible".

제한

힌트