1.


/**
* ACM Training 2009
* ACM Problem #10307 - Killing Aliens in Borg Maze
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1248
*
* @author Dennis Wilfert
* @version 1.0, 09/13/2009
*
* Methode: Graphen (BFS, Prim)
* Status : Accepted
* Runtime: 0.316
*/
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));

StringTokenizer token;

int cases = Integer.parseInt(reader.readLine());
int x, y, j, i, k, aliens, length, head, sum, begin, end;
char[][] field;
int[][] field2;
boolean[] nodes;
int[][] alienList;
int max = 2500;
int[][] ways;
int[][] queue;
int[][] coordinates = new int[101][2];

while (cases > 0) {

token = new StringTokenizer(reader.readLine());

x = Integer.parseInt(token.nextToken());
y = Integer.parseInt(token.nextToken());
field = new char[y][];
field2 = new int[y][x];

// Zeilenweise einlesen und in char-Array speichern
for (i = 0; i < y; i++) {
field[i] = reader.readLine().toCharArray();
}

// Anzahl der Aliens
aliens = 0;

// A und S suchen, und die Koordinaten Speichern
for (i = 0; i < y; i++) {
for (j = 0; j < x; j++) {
if (field[i][j] == 'A' || field[i][j] == 'S') {
coordinates[aliens][0] = i;
coordinates[aliens++][1] = j;
}
}
}

// Minimale Weglängen zwischen allen Aliens
ways = new int[aliens][aliens];

/////////////////Breitensuche/////////////////

for (i = 0; i < aliens; i++) {
// Maximale anzahl an Schritten für alle Felder eintragen
for (j = 0; j < y; j++) {
for (k = 0; k < x; k++) {
field2[j][k] = max;
}
}

begin = 0;
end = 1;
queue = new int[max][3];
queue[0][0] = coordinates[i][0];
queue[0][1] = coordinates[i][1];

field2[queue[0][0]][queue[0][1]] = 0;

while (end > begin) {
int r = queue[begin][0];
int c = queue[begin][1];
int cost = queue[begin++][2] + 1;

if (field[r][c] == 'S' || field[r][c] == 'A') {
for (j = 0; j < aliens; j++) {
if (coordinates[j][0] == r && coordinates[j][1] == c) {
ways[i][j] = cost - 1;
}
}
}

// Prüfen ob um die aktuelle Position herum eine Raute ist
if (field2[r + 1][c] > cost && field[r + 1][c] != '#') {
field2[r + 1][c] = cost;
queue[end][0] = r + 1;
queue[end][1] = c;
queue[end++][2] = cost;
}
if (field2[r - 1][c] > cost && field[r - 1][c] != '#') {
field2[r - 1][c] = cost;
queue[end][0] = r - 1;
queue[end][1] = c;
queue[end++][2] = cost;
}
if (field2[r][c + 1] > cost && field[r][c + 1] != '#') {
field2[r][c + 1] = cost;
queue[end][0] = r;
queue[end][1] = c + 1;
queue[end++][2] = cost;
}
if (field2[r][c - 1] > cost && field[r][c - 1] != '#') {
field2[r][c - 1] = cost;
queue[end][0] = r;
queue[end][1] = c - 1;
queue[end++][2] = cost;
}
}
}
//////////////////////////////////////////////

alienList = new int[(aliens * aliens) - aliens][5];
k = 0;
length = alienList.length;

// Liste für den Prim-Algorithmus erstellen
for (i = 0; i < aliens; i++) {
for (j = 0; j < aliens; j++) {
if (i != j) {
alienList[k][0] = i;
alienList[k][1] = j;
alienList[k++][2] = ways[i][j];
}
}
}

sort(alienList, 0, length - 1);

// Jeweils die vorherigen und die nächste Position zu jedem Wert eintragen
for (i = 0; i < length; i++) {
alienList[i][3] = i - 1;
alienList[i][4] = i + 1;
}

head = 0;
nodes = new boolean[aliens];
nodes[0] = true;
sum = 0;
// Alle Knoten durchlaufen
for (j = aliens - 1; j > 0; j--) {
i = head;
while (i < length) {
// Steht weder der Anfangs- noch der Endknoten der Stra�e auf true wird mit dem nächsten Wert weitergemacht
if (!nodes[alienList[i][0]] && !nodes[alienList[i][1]]) {
i = alienList[i][4];
} // Steht mindestens einer der Beiden Knoten der aktuellen Stra�e auf true
else {
// Ist der Vorgängerwert -1, bekommt die nachfolgende Stra�e auch -1 als Vorgängerwert
if (alienList[i][3] == -1) {
alienList[alienList[i][4]][3] = alienList[i][3];
} // Ansonsten bekommt die vorherige Stra�e den nachfolgerwert als nächste Stra�e
// und doie nachfolgende Stra�e die Vorgängerstra�e als vorherige Stra�e
else {
alienList[alienList[i][3]][4] = alienList[i][4];
alienList[alienList[i][4]][3] = alienList[i][3];
}
// Ist nur einer der beiden Knotenpunke der Stra�e auf true wird der andere Knotenpunkt auch auf true gesetzt und die Länge
// der Stra�e von der Gesamtlänge des Stra�ennetzes abgezogen, d.h. die Stra�e kann ohne Beleuchtung auskommen.
if ((nodes[alienList[i][1]] && !nodes[alienList[i][0]]) || (nodes[alienList[i][0]] && !nodes[alienList[i][1]])) {
nodes[nodes[alienList[i][1]] ? alienList[i][0] : alienList[i][1]] = true;
sum += alienList[i][2];
// Ist der Vorgängerwert -1 wird der Nachfolgerwert als Startpunkt für die while-Schleife gesetzt, ansonsten wird mit
// dem alten Startwert begonnen
if (alienList[i][3] == -1) {
head = alienList[i][4];
}
// Schleife unterbrechen
break;
}
i = alienList[i][4];
}
}
}
writer.println(sum);

cases--;
}
writer.flush();
}

static void sort(int[][] a, int start, int end) {
int[] tmp;
int i = start;
int j = end;
int x = a[(start + end) / 2][2];

do {
// Vom Startpunkt aus einen Wert suchen der >= x ist
while (a[i][2] < x) {
i++;
}
// Vom Endpunkt aus einen Wert suchen der <= x ist
while (a[j][2] > x) {
j--;
}

// a[i] und a[j] tauschen
if (i <= j) {
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j--;
}
} while (i <= j);

if (start < j) {
sort(a, start, j);
}

if (i < end) {
sort(a, i, end);
}
}
}