Problem A: 迷宫

Problem A: 迷宫

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 235  Solved: 34
[Submit] [Status] [Web Board] [Creator:]

Description

三体人是来自居住在距离太阳系4光年外的半人马座α星的一个神奇种族。他们的集体之间是共脑的,也就是说每个三体人都通过一个复杂的空间网络与集体联系在一起,这样可以使得每个成员都能公用知识和对危险的感知。另外,三体人非常喜欢跑到迷宫中自闭2333.
您的任务是帮助三体人,开发一个程序,帮助三体人扫描迷宫,以使得神经网络连接到每个躲在迷宫中的三体人并返回最小的成本(是的,真的,他们并不优秀)。
迷宫中有若干个三体人和一个用于共脑的‘服务器’。现在你需要将所有的三体人都通过神经网络直接或间接的连接到服务器上,连接方式只有上下左右。成本是神经网络的总长度。
为了便于处理,迷宫是二维的平面图,其中'#'是障碍物,'a'是三体人,'S'是服务器。另外,迷宫总是封闭的,即无法从服务器的位置走到迷宫之外。

Input

单次输入中,有一个整数,N<=50,表示测试用例数。
每个测试用例的第一行包含两个整数x,y代表迷宫的长与宽,保证1<=x,y<=50。
之后的x行,每一行有y个字符。

Output

对于每个测试用例,输出一行,表示将迷宫中的所有三体人连接至服务器所需的最低成本。
如果不能使所有三体人连接至服务器输出-1。

Sample Input Copy

2
5 6
##### 
#A#A##
# # A#
#S  ##
##### 
7 7
#####  
#AAA###
#    A#
# S ###
#     #
#AAA###
#####  

Sample Output Copy

8
11