题目描述

博格人(Borg)是来自银河系第四象限的一种经过强化的类人种族，拥有极其强大的力量。博格集体(Borg collective)是指博格文明群体意识的统称。每个博格个体都通过精密的子空间网络与集体相连，确保每个成员都能得到持续的监督和指导。

你的任务是帮助博格人（没错，真的）开发一个程序，用于估算在迷宫中扫描并同化隐藏的外星人所需的最小成本。搜索过程中可以向上、下、左、右四个方向移动。棘手的是，搜索开始时由超过100个个体组成的大群体进行。每当同化一个外星人，或者在搜索开始时，群体可以分裂成两个或更多小组（但它们的意识仍然是集体的）。搜索迷宫的成本定义为所有参与搜索的群体移动的总距离。例如，如果原始群体移动了$5$步，然后分裂成两个各移动$3$步的小组，那么总成本就是$11=5+3+3$。

输入格式

第一行输入一个整数$N \leq 50$，表示测试用例的数量。每个测试用例以两个整数$x$、$y$（$1 \leq x,y \leq 50$）开始，表示迷宫的宽度和高度。接下来是$y$行，每行包含$x$个字符。每个字符的含义如下：

• 空格 表示可通过的空地
• #表示障碍墙
• A表示外星人
• S表示搜索起点

迷宫的边缘总是封闭的，即无法从S的位置离开迷宫。每个迷宫中外星人的数量不超过$100$个，且所有外星人都可以被到达。

输出格式

对于每个测试用例，输出一行，表示成功搜索迷宫并消灭所有外星人的最小成本。

输入样例 1

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

输出样例 1

8
11

题目来源

2001年瑞典/挪威编程锦标赛