1. 


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #784 (Maze Exploration)
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=9&problem=725&mosmsg=Submission+received+with+ID+7211431
*
* @author Christian Posselt
* @author Jonathan Schubert
* @version 1.0, 06/25/2009
*
* Status : Accepted
* Runtime: 0.770
*/

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

public class Main
{
public static int[] dy = new int[]{-1,-1,-1, 0,0, 1,1,1};
public static int[] dx = new int[]{-1, 0, 1,-1,1,-1,0,1};


public static void main(String... args) throws IOException
{
//set up all variables needed
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder part = new StringBuilder();
StringBuilder answer = new StringBuilder();
//lineLength saves the length of all input lines
HashMap<Integer, Integer> lineLength = new HashMap<Integer, Integer>();
String line;
int row, amount;

//amount of testcases
amount = Integer.parseInt(reader.readLine());

for(int i=1; i <= amount; i++)
{
lineLength = new HashMap<Integer, Integer>();

part = new StringBuilder();
line = reader.readLine();

int point_row = 0;
int point_col = 0;

row = 1;
//while line has figures except '_', it is the maze of this testcase
while(!line.contains("_") && !line.equals(""))
{
lineLength.put(row, line.length());
for(int j=0; j<line.length();j++)
{
//remember cell to start with
if(line.charAt(j) == '*')
{
part.append('#');
point_row = row;
point_col = j;
}
else
part.append(line.charAt(j));
}

row++;

if(reader.ready())
line = reader.readLine();
else
line = "";
}

//draw all neighbor cells
neighbors(point_row,point_col, part, lineLength);

//put line breaks back into the String
for(int l=1, k=lineLength.get(l);l<lineLength.size();)
{
part.insert(k++, "\n");
l++;
k += lineLength.get(l);
}

answer.append(part);

//leave line with '_' as is
answer.append("\n"+line+"\n");
}

System.out.print(answer.toString());
}

/**
* Neihbors gets all cells connected to a starting cell recursively and puts a '#'
* at those positions
*
* @param row: int for the row to start in
* @param col: int for the col to start with
* @param answer: StringBuilder to put the '#' into.
* @param lineLength: HashMap<Integer, Integer> contains the lineLength for index calculation
*/
public static void neighbors(int row, int col, StringBuilder answer, HashMap<Integer,Integer> lineLength)
{
//test all eight neighbors
for(int i=0;i<8;i++)
{
int index = 0;
for(int j=1; j<row+dy[i];j++)
index += lineLength.get(j);
index += col + dx[i] -1;

//index within room and empty cell?
if(index <= answer.length() && answer.charAt(index) == ' ')
{
answer.setCharAt(index, '#');
neighbors(row+dy[i],col+dx[i],answer,lineLength);
}
}
}
}


2.

/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #784 Maze Exploration
* Link: http://uva.onlinejudge.org/external/7/784.pdf
*
* @author Schirm , Mathauser , Mohr

* @version 1.0, 07/05/2009
*
* Status : Accepted
* Runtime: 1.688
*/

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

public static void main(String... args) {
Scanner sc = new Scanner(System.in);
int cases = Integer.parseInt(sc.nextLine());

while (cases > 0) {

// Koordinaten des Sterns
int starIndex = 0;
int starPos = 0;

// Jede Zeile des Spielfelds auf einen String addieren und ein '_'
// als End of Line Zeichen hinzufügen
String fieldString = "";
String line = sc.nextLine();
while (line.isEmpty()) {
System.out.println();
line = sc.nextLine();
}
int countLine = 0;
while (!line.startsWith("_")) {

// Position des Sterns speichern
if (line.contains("*")) {
starIndex = countLine;
starPos = line.indexOf('*');
}
fieldString += line + "\n_";

// Nächste Zeile lesen
line = sc.nextLine();
countLine++;
}

// String an '_' splitten
String[] tmp = fieldString.split("_");

// Spielfeld als 2D String-Array speichern
char[][] field = new char[tmp.length][];
for (int i = 0; i < tmp.length; i++)
field[i] = tmp[i].toCharArray();

ArrayList<ArrayList<Integer>> toDoList = new
ArrayList<ArrayList<Integer>>();
ArrayList<Integer> cords = new ArrayList<Integer>();

// Stern als Startpunkt in die toDoListe eintragen
cords.add(starIndex);
cords.add(starPos);
toDoList.add(cords);

while (!toDoList.isEmpty()) {
// Element aus der toDoList holen
ArrayList<Integer> element = toDoList.get(0);
starIndex = element.get(0);
starPos = element.get(1);

// Element im Feld erstetzen
field[starIndex][starPos] = '#';

// Freie Nachbarn in die toDoListe eintragen
if (field[starIndex - 1][starPos] == ' ') {
cords = new ArrayList<Integer>();
cords.add(starIndex - 1);
cords.add(starPos);
if (!toDoList.contains(cords))
toDoList.add(cords);
}

if (field[starIndex][starPos - 1] == ' ') {
cords = new ArrayList<Integer>();
cords.add(starIndex);
cords.add(starPos - 1);
if (!toDoList.contains(cords))
toDoList.add(cords);
}

if (field[starIndex][starPos + 1] == ' ') {
cords = new ArrayList<Integer>();
cords.add(starIndex);
cords.add(starPos + 1);
if (!toDoList.contains(cords))
toDoList.add(cords);
}

if (field[starIndex + 1][starPos] == ' ') {
cords = new ArrayList<Integer>();
cords.add(starIndex + 1);
cords.add(starPos);
if (!toDoList.contains(cords))
toDoList.add(cords);
}

// Aktuelles Element aus der toDoList entfernen
toDoList.remove(0);
}

// Ausgabe
for (char[] charLine : field)
System.out.print(charLine);

// Underscore Zeile
System.out.println(line);

cases--;
}
}
}

3.

/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #784 - (Maze expolaration)
* http://uva.onlinejudge.org/external/7/784.pdf
*
* @author Fabian Seidl
* @author Marcel Sachse
* @version 1.0, 07.07.2009
*
* Status : Accepted
* Runtime: 2.680
*/


import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;


public class Main {
public static void main(String[] args) throws IOException
{
BufferedInputStream bin = new BufferedInputStream(System.in);
Scanner scanner = new Scanner(bin);

int cases= Integer.parseInt(scanner.nextLine());
while(cases!=0)
{
char[][] rooms= new char[31][80];
String line=scanner.nextLine();
int lines=0;
int posx=0;
int posy=0;

while(!line.startsWith( "_"))
{
for (int i=0;i<line.length();i++)
{
char tmp;
tmp=line.charAt(i);
if(tmp=='*')
{
posx=i;
posy=lines;
tmp='#';
}
rooms[lines][i]=tmp;
}

if(scanner.hasNextLine())
line=scanner.nextLine();
lines++;
}

for (int i=0;i<line.length();i++)
{
char tmp;
tmp=line.charAt(i);
if(tmp=='*')
{
posx=i;
posy=lines;
tmp='#';
}
rooms[lines][i]=tmp;
}

fill(posx,posy,rooms);
Output(rooms);
lines=0;
cases--;
}
}

static void fill(int x, int y, char[][] room)
{
for (int i=-1;i<2;i++)
for (int j=-1;j<2;j++)
if(room[y+i][x+j]==' ')
{
room[y+i][x+j]='#';
fill(x+j,y+i,room);
}
}

public static void Output(char[][] room)
{
for (int i=0;i<31;i++)
{
if(room[i][0]==(char)0)break;
for (int j=0;j<80;j++)
{
if(room[i][j]==(char)0)break;
System.out.print(room[i][j]);
}
System.out.println();
}
}

}