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);
}
}


2.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 10307 Killing Aliens in Borg Maze
* Link:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&page=show_problem&problem=1248
*
* @author Patrick Bédat
* @version 1.0, 14.11.2010
*
* Method : BFS, Prim
* Status : Accepted
* Runtime: 2.252
*/
package graphs.mst.borgMaze;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main
{

static BufferedReader reader;
static int[][] distances;
static HashSet<Integer> aliens = new HashSet<Integer>();
static int start;
static boolean[] openSpace;
static int width;
static int height;
static HashMap<Integer, LinkedList<Integer>> neighbours;

public static void main(String... args) throws IOException
{
reader = new BufferedReader(new InputStreamReader(System.in));

int nTestCases = Integer.parseInt(reader.readLine());

for (int tc = 0; tc < nTestCases; tc++)
{
Solve();
}
}

static void Solve() throws IOException
{
StringTokenizer st = new StringTokenizer(reader.readLine());

width = Integer.parseInt(st.nextToken());
height = Integer.parseInt(st.nextToken());

distances = new int[width * height][width * height];

neighbours = new HashMap<Integer, LinkedList<Integer>>();

openSpace = new boolean[height * width];

readMaze(width, height);

HashSet<Integer> newGraphVerticies = new HashSet<Integer>();
newGraphVerticies.add(start);

PriorityQueue<Edge> queue = new PriorityQueue<Edge>();

for (Integer alien : aliens)
{
queue.add(new Edge(start, alien));
}

int totalCost = 0;

while (!aliens.isEmpty() && !queue.isEmpty())
{
Edge currentEdge = queue.poll();

if (newGraphVerticies.contains(currentEdge.to))
{
continue;
}

totalCost += currentEdge.cost;

newGraphVerticies.add(currentEdge.to);

aliens.remove(currentEdge.to);

for (Integer alien : aliens)
{
Edge newEdge = new Edge(currentEdge.to, alien);
queue.add(newEdge);
}
}

System.out.println(totalCost);
}

private static void readMaze(int width, int height) throws IOException
{
aliens = new HashSet<Integer>();
for (int y = 0; y < height; y++)
{
char[] line = reader.readLine().toCharArray();

for (int x = 0; x < line.length; x++)
{
int nextID = y*width + x;

if (line[x] != '#')
openSpace[nextID] = true;

if (line[x] == 'A')
aliens.add(nextID);
else if (line[x] == 'S')
start = nextID;
}
}
}

private static int searchBFS(Integer from, Integer to)
{
if (distances[from][to] != 0)
return distances[from][to];

HashMap<Integer, Integer> dists = new HashMap<Integer, Integer>();
dists.put(from, 0);
PriorityQueue<Integer> stack = new PriorityQueue<Integer>(100, new NodeComparator(dists));
stack.add(from);

while (!stack.isEmpty())
{
Integer current = stack.poll();
distances[from][current] = dists.get(current);

if (current == to)
{
break;
}

for (Integer neighbour : getNeighbours(current))
{
Integer distToNeighbour = dists.get(neighbour);

if (distToNeighbour == null || dists.get(current) + 1 < distToNeighbour)
{
distances[current][neighbour] = 1;
dists.put(neighbour, dists.get(current) + 1);
stack.add(neighbour);
}
}
}

return dists.get(to);
}

static LinkedList<Integer> getNeighbours(int id)
{
if (neighbours.containsKey(id))
return neighbours.get(id);

LinkedList<Integer> neigbhours = new LinkedList<Integer>();

if (id-width > 0 && openSpace[id - width])
neigbhours.add(id - width);
if (id+1 < openSpace.length && openSpace[id + 1])
neigbhours.add(id + 1);
if (id-1 > 0 && openSpace[id - 1])
neigbhours.add(id - 1);
if (id+width < openSpace.length && openSpace[id + width])
neigbhours.add(id + width);
return neigbhours;
}

static class NodeComparator implements Comparator<Integer>
{

private Map<Integer, Integer> dists;

public NodeComparator(HashMap<Integer, Integer> dists)
{
this.dists = dists;
}

public int compare(Integer o1, Integer o2)
{
int d1 = dists.get(o1);
int d2 = dists.get(o2);

if (d1 < d2)
return -1;
if (d1 > d2)
return 1;
return 0;
}
}

static class Edge implements Comparable<Edge>
{

public Integer from;
public Integer to;
public int cost;

public Edge(int from, int to)
{
this.from = from;
this.to = to;

this.cost = searchBFS(from, to);
}

public int compareTo(Edge o)
{
if (cost < o.cost)
return -1;
if (cost > o.cost)
return 1;
return 0;
}
}
}