Description

F学长刚刚制作好的养生茶被坏同学偷偷的放在了迷宫里的一个地方。

迷宫用N*M​的矩阵表示（​N,M<=100）矩阵中的每项可以代表道路('@')，墙壁('#')和高数题('x')年轻的F学长('r')决定去寻找他的养生茶('a')，由于坏同学在路上放了很多高数题，F学长必须解决高数题后才能继续前进，每移动一个位置需要花费1个单位时间，做出一道高数题也需要1个单位时间，同时F学长非常聪明，能做出所有的高数题。

给定迷宫，养生茶，F学长和高数题的位置，计算找到养生茶所需要的最短时间。

Input Format

第一行t，表示有t组数据

每组数据有n,m，代表迷宫行和列

迷宫中'@'代表道路，'a'代表养生茶，'r'代表F学长，'x'代表高数题，'#'代表墙壁

Output Format

如果F学长能找到他的养生茶，输出行动所需最短时间，否则输出Impossible

1
7 8
#@#####@
#@a#@@r@
#@@#x@@@
@@#@@#@#
#@@@##@@
@#@@@@@@
@@@@@@@@​

13​

Source

搜索