1. 
package acm_10307_killing_aliens_in_borg_maze;

/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: acm_10307_killing_aliens_in_borg_maze
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=15&problem=1248
*
* @author Martin Lambeck
* @version 1.0, 10.08.2010
*
* Method : bfs, mst
* Status : Accepted
* Runtime: 0.600
*/

import java.util.*;

public class Main
{
final static int WALL = -1;
final static int FREE = -2;

static Scanner sc = new Scanner(System.in);

public static void main(String... args)
{
int cases = sc.nextInt();

for (int i = 0; i < cases; i++)
testcase();

}

static void testcase()
{
int w = sc.nextInt(); //width
int h = sc.nextInt(); //height

sc.nextLine(); //skip the \n


int counter = 1; //number of nodes

char[] line = new char[w]; //line of input
int[][] maze = new int[h][w]; // -2/-1 = FREE/WALL; 0 = start point; >0 id of alien
int[][] nodes; //adjacency matrix
//List<Alien> aliens = new ArrayList<Alien>(101);

for (int i = 0; i < h; i++)
{
//parse a line of input
line = sc.nextLine().toCharArray();

for (int j = 0; j < w; j++)
{
switch (line[j])
{
case ' ':
maze[i][j] = FREE;
break;

case '#':
maze[i][j] = WALL;
break;

case 'A':
maze[i][j] = counter;
counter++;
break;

case 'S':
maze[i][j] = 0;
break;
}
}
}

nodes = new int[counter][counter]; //adjacency matrix

for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
if (maze[i][j] >= 0) //here is an alien or the start point
bfs(nodes[maze[i][j]], maze, new Point(i, j)); //do bfs to find edges to any other nodes (aliens + start)


int count = mst(nodes); //sum of weights of mst

System.out.println(count);
}

//bfs to find distance to all other aliens + start
//nodes will be filled with the distance to node i, where i = array index
//pos = position from where to start the search
static void bfs(int[] nodes, int[][] maze, Point pos)
{
boolean[][] visited = new boolean[maze.length][maze.length];
LinkedList<Point> q = new LinkedList<Point>();
Point p;

int x, y;

int step = -1; //distance = costs for edge

q.add(pos);

while (q.size() > 0)
{
int nb = q.size();

step++;

for (int i = 0; i < nb; i++)
{
p = q.pollFirst();

x = p.x;
y = p.y;

if (visited[x][y])
continue;

visited[x][y] = true;

//add any neighbor field (NSEW) to queue, which is not a wall, and is unvisited
if (maze[x+1][y] != WALL && !visited[x+1][y])
q.add(new Point(x+1, y));

if (maze[x][y+1] != WALL && !visited[x][y+1])
q.add(new Point(x, y+1));

if (maze[x-1][y] != WALL && !visited[x-1][y])
q.add(new Point(x-1, y));

if (maze[x][y-1] != WALL && !visited[x][y-1])
q.add(new Point(x, y-1));

//if node, add it to the array of edges
if (maze[x][y] >= 0)
{
nodes[maze[x][y]] = step;
}
}
}
}


static public int mst (int[][] nodes)
{
PriorityQueue<Edge> pq = new PriorityQueue<Edge>(101*101);
boolean[] visited = new boolean[nodes.length];
int node;
Edge e;
int costs = 0;

//add all edges of start point
for (int i = 1; i < nodes.length; i++)
{
pq.add(new Edge(i, nodes[0][i]));
}

visited[0] = true;

while (pq.size() > 0)
{
e = pq.poll(); //get cheapest edge

node = e.to;

if (visited[node]) //if the node was already visited (mst already contains this vertex) skip this edge
continue;

visited[node] = true;


costs += e.costs; //add costs of edge

//add all edges (to yet unvisited points) from this point
for (int i = 0; i < nodes.length; i++)
{
if (!visited[i])
{
pq.add(new Edge(i, nodes[node][i]));
}
}

}

return costs;
}
}

class Point
{
int x, y;

public Point(int xx, int yy)
{
x = xx;
y = yy;
}
}
class Edge implements Comparable<Edge>
{
int to;
int costs;

public Edge(int t, int c)
{
to = t;
costs = c;
}

public int compareTo(Edge other)
{
if (costs == other.costs)
return 0;

return (costs < other.costs ? -1 : 1);
}
}