1.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* 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 Burgmair Stefan
* @author YYY
* @version 1.0, 17/05/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 1.116
*/

public class Main
{
static char[][] map;
static int[][] madeSteps;
static int[][] nodes;
static int[][] distances;

static int startingRow;
static int startingCol;

static ArrayList<Integer> rows = new ArrayList<Integer>();
static ArrayList<Integer> cols = new ArrayList<Integer>();
static ArrayList<Integer> doneSteps = new ArrayList<Integer>();

public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int numberOfCases = Integer.parseInt(reader.readLine());
for(int g = 0; g < numberOfCases; g++){
String arr [] = reader.readLine().split(" ");
int mapSizeX = Integer.parseInt(arr[0]);
int mapSizeY = Integer.parseInt(arr[1]);
map = new char [mapSizeY][mapSizeX];
madeSteps = new int [mapSizeY][mapSizeX];
int nmbrOfAliens = 0;
int rowOfStart = 0;
int colOfStart = 0;

for(int h = 0; h < mapSizeY; h ++){
String input = reader.readLine();
for(int i = 0; i < input.length(); i ++){
map[h][i] = input.charAt(i);
if(input.charAt(i) == 'A'){
nmbrOfAliens ++;
}
else if (input.charAt(i) == 'S'){
colOfStart = i;
rowOfStart = h;
}
}
}
nodes = new int[nmbrOfAliens + 1][2];
distances = new int [nmbrOfAliens + 1][nmbrOfAliens + 1];

//fill nodes
map[rowOfStart][colOfStart] = 'A';

for(int h = 0; h < mapSizeY; h ++)
for(int i = 0; i < mapSizeX; i ++){
if(map[h][i] == 'A')
for (int j = 0; j <= nmbrOfAliens; j++)
if(nodes[j][0] == 0 && nodes[j][1] == 0){
nodes[j][0] = h;
nodes[j][1] = i;
break;
}
}

//find distances:
for (int i = 0; i <= nmbrOfAliens; i++){
for(int h = 0; h < mapSizeY; h ++)
for(int f = 0; f < mapSizeX; f ++){
madeSteps[h][f] = -1;
}
rows.add(nodes[i][0]);
cols.add(nodes[i][1]);
doneSteps.add(1);
startingRow = nodes[i][0];
startingCol = nodes[i][1];
madeSteps[nodes[i][0]][nodes[i][1]] = 0;
findAllAliens(nodes[i][0], nodes[i][1]);
//printMap(madeSteps, false);
}

// find MST
int output = 0;
int indexOfShortestPath = 0;
int shortestDistance = 0;
boolean [] isUsed = new boolean [nmbrOfAliens + 1];
for (int i = 0; i <= nmbrOfAliens; i++)
isUsed[i] = false;

// search through each node once:
for (int i = 0; i <= nmbrOfAliens; i++){
// search through visited nodes:
for (int j = 0; j <= nmbrOfAliens; j++){
// search through the paths of visited nodes:
if(isUsed[j] == true){
for (int k = 0; k <= nmbrOfAliens; k++){
if(isUsed[k] == false){
if(shortestDistance == 0 || shortestDistance > distances[k][j]){
shortestDistance = distances[k][j];
indexOfShortestPath = k;
//System.out.println(shortestDistance + " " + j);
}
}
}
}
}
isUsed[indexOfShortestPath] = true;
output = output + shortestDistance;
// System.out.println("out: " + output);
// System.out.println("dist: " + shortestDistance);
shortestDistance = 0;
}

System.out.println(output);
}
}

static void findAllAliens(int curRow, int curCol){

while(rows.isEmpty() == false){
if(isValid(rows.get(0) - 1, cols.get(0))){
isAlien(rows.get(0) - 1, cols.get(0), doneSteps.get(0));
rows.add(rows.get(0) - 1);
cols.add(cols.get(0));
doneSteps.add(doneSteps.get(0) + 1);
}
if(isValid(rows.get(0), cols.get(0) - 1)){
isAlien(rows.get(0), cols.get(0) - 1, doneSteps.get(0));
rows.add(rows.get(0));
cols.add(cols.get(0) - 1);
doneSteps.add(doneSteps.get(0) + 1);
}
if(isValid(rows.get(0) + 1, cols.get(0))){
isAlien(rows.get(0) + 1, cols.get(0), doneSteps.get(0));
rows.add(rows.get(0) + 1);
cols.add(cols.get(0));
doneSteps.add(doneSteps.get(0) + 1);
}
if(isValid(rows.get(0), cols.get(0) + 1)){
isAlien(rows.get(0), cols.get(0) + 1, doneSteps.get(0));
rows.add(rows.get(0));
cols.add(cols.get(0) + 1);
doneSteps.add(doneSteps.get(0) + 1);
}
rows.remove(0);
cols.remove(0);
doneSteps.remove(0);
}
}
static int count = 0;
static boolean isValid(int curRow, int curCol){
if(map[curRow][curCol] == '#')
return false;
if(madeSteps[curRow][curCol] > -1)
return false;
return true;
}

static void isAlien(int curRow, int curCol, int doneSteps){
madeSteps[curRow][curCol] = doneSteps;
if(map[curRow][curCol] == 'A'){
for(int i = 0; i < nodes.length; i++)
if(nodes[i][0] == curRow && nodes[i][1] == curCol){
for(int j = 0; j < nodes.length; j++)
if(nodes[j][0] == startingRow && nodes[j][1] == startingCol){
distances [j][i] = doneSteps;
break;
}
break;
}
}
}

public static void printMap(int[][] map, boolean isLastOutput)
{
for (int x = 0; x < map.length; x ++)
{
for (int y = 0; y < map[0].length; y ++)
{
System.out.print(map[x][y]);
if (y + 1 < map.length)
System.out.print(" ");
}
if (x + 1 < map.length | isLastOutput == false)
System.out.println();
}
if (isLastOutput == false)
System.out.println();
}


--------------------------------------------------------------------------------------------------------------------
}




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