1.


/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09 Problem: 784 - Maze Exploration
* http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=9&page=show_problem&problem=725
*
* @author Kratzer Kevin
* @version 1.0, 12/23/2009
*
* Method : Ad-Hoc Status : Accepted Runtime: 0.980
*/


public class Main784 {

public static void main(String... args) {
Scanner s = new Scanner(System.in);
Status[][] maze = new Status[30][80];
newMaze(maze);
int max = s.nextInt();
while (max > 0) {
max--;
int startLine = 0;
int startColumn = 0;
for(int lineIndex = 0; true; lineIndex++) {
String line = s.nextLine();
if(line.matches("_____")) {
walkMaze(maze,startLine,startColumn);
printMaze(maze);
System.out.println("_____");
newMaze(maze);
break;
} else {
for(int i = 0; i < line.length(); i++) {
if(line.charAt(i) == 'X') {
maze[lineIndex][i] = Status.Wall;
} else if(line.charAt(i) == ' ') {
maze[lineIndex][i] = Status.Free;
} else if(line.charAt(i) == '*') {
maze[lineIndex][i] = Status.Free;
startLine = lineIndex;
startColumn = i;
}
}
}
}


}
}

private static void printMaze(Status[][] maze) {
StringBuilder builder = new StringBuilder(2400);
for(int line = 0; line < 30; line++) {
boolean end = false;
StringBuilder lineBuilder = new StringBuilder(80);
for(int col = 0; col < 80; col++) {
if(maze[line][col] == Status.Unused && end) {
break;
}
if(maze[line][col] == Status.Unused || maze[line][col] == Status.Free) {
lineBuilder.append(' ');
} else if(maze[line][col] == Status.Walked) {
lineBuilder.append('#');
end = true;
} else if(maze[line][col] == Status.Wall) {
lineBuilder.append('X');
end = true;
}
}
String lineString = lineBuilder.toString();
if(!lineString.matches(" *")) {
builder.append(lineString);
builder.append("\n");
}
}
System.out.println(builder.substring(0, builder.length()-1));

}

private static void walkMaze(Status[][] maze, int startLine, int startColumn) {
if(maze[startLine][startColumn] != Status.Free) {
return;
}
maze[startLine][startColumn] = Status.Walked;
walkMaze(maze,startLine-1,startColumn);
walkMaze(maze,startLine+1,startColumn);
walkMaze(maze,startLine,startColumn-1);
walkMaze(maze,startLine,startColumn+1);
}

private static Status[][] newMaze(Status[][] maze) {
for(int i = 0; i < 30; i++) {
Arrays.fill(maze[i], Status.Unused);
}
return maze;
}

private enum Status {
Wall,Free,Walked,Unused
}

}