Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem A: 打败魔王

Problem A: 打败魔王

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 52  Solved: 13
[Submit][Status][Web Board]

Description

为了打败邪恶魔王,小智需要集齐迷宫中的若干颗龙珠(龙珠总数不会超过7颗),并到达神龙巢穴,召唤神龙。给定迷宫的地图,‘@’代表小智现在的位置,‘#’代表障碍,‘*’代表可行走区域,‘$’代表龙珠,‘&’代表神龙巢穴,小智可以向上下左右4个方向移动,每次移动需要1秒时间,问最少需要多少时间,可以集齐需要的龙珠,并召唤神龙。如若不能召唤神龙,则输出”Impossible!”

Input

多组样例,每组样例首行三个整数nmk,分别代表迷宫长和宽,以及需要集齐的龙珠数量(2<=nm<=10, 0<=k<=7)。随后,nm列字符代表地图。

Output

对于每组样例,若能够召唤神龙,则每行输出最短时间,否则,输出“Impossible”。

Sample Input

4 3 3
@#$
*$*
$#*
$*&
3 3 5
@&*
***
#$$
3 3 3
#@#
$#$
&$.

Sample Output

7
Impossible
Impossible

HINT

[Submit][Status][Web Board]