/*******************************************************************************
 * COP3503 Summer 05
 * Project 2 Key
 * 
 * The general idea of this solution is as follows:
 * 
 * For each grid in the input file,
 * 1) create a new instance of the solution
 * 2) read the file
 * 3) solve the problem
 * 4) print the solution
 * 
 * Given this, the most difficult part of the problem is to solve it.
 * Considering the assignment elicits to do this with recursion, we have
 * a start.  In recursion, we have 4 things we must do:
 * 
 * 1) Clearly define the function in terms of input size.  For this
 * problem, given a potential place to move (x, y) and the type of
 * square we came from, we will fill in the map with the 'R' symbol.
 * The will use the number of unmarked 'R' symbols to define the
 * problem size.
 * 
 * 2) Establish a basis problem.  This means, find a problem that is
 * trivial to solve.  With this problem, the basis is when there is no
 * where else to go.  Once we reach a state where there are no more
 * squares to move into, the problem is trivial... don't move anymore!
 * 
 * 3) Break the problem into subproblems.  In our case, we can solve any
 * problem with fewer unmarked squares by calling the recursive function
 * because we are shrinking the input size.  So this lends to marking
 * at least one square and going every possible way that we can from
 * the current square.  Valid movement is crearly defined in the problem
 * specification.
 * 
 * 4) Combine the subproblems into a solution.  We do this by merging
 * all of the recursive movement answers and the "current" square.
 * The current square is what allows us to shrink the problem, so we
 * need to verify that it is valid before moving.
 ******************************************************************************/

import java.io.*;

public class project2key {

	/**************************************************************************
	 * The main function is responsible for handling IO errors, setting
	 * up the sub problems, and executing the interface functions on the
	 * instance objects.
	 *************************************************************************/
	public static void main(String []args) {
		try {
			
			/******************************************************************
			 * This opens the file and then reads in how many cases are in the
			 * file.
			 *****************************************************************/
			BufferedReader input = new BufferedReader(new FileReader("grid.in"));
			int numberOfItems = Integer.parseInt(input.readLine().trim());

			/******************************************************************
			 * For each instance in the file, create a new instance of the
			 * solution object given the specified dimensions.  Then process
			 * the prescribed algorithm (read, solve, print).
			 *****************************************************************/

			for(int i = 1; i <= numberOfItems; i++) {
				int dimensions = Integer.parseInt(input.readLine().trim());

				project2key solver = new project2key(dimensions, dimensions);
				solver.read(input);
				solver.solve();

				System.out.println("Reachable Map #" + i);
				solver.print();
				System.out.println();
			}

			input.close();

		}
			
		/**********************************************************************
		 * Any errors that occur will be caught here.  I was aiming for File
		 * IO errors, but this will also catch array index exceptions.
		 * you should try to never have the main function throw exceptions.
		 *********************************************************************/

		catch(Exception exception) {
			exception.printStackTrace();
		}

	}

	/**************************************************************************
	 * The consctructor creates a new problem given the x/y dimensions of the
	 * grid.  It also initializes the starting positions to -1 to throw an
	 * exception if an 'X' is not specified in the file. It's not a "good" way
	 * to handle this, but will work....
	 *************************************************************************/

	public project2key(int sizex, int sizey) {
		gridCells = new char[sizex][sizey];
		startX = startY = -1;
	}

	/**************************************************************************
	 * the read function reads in the grid.  The size of the grid is specified
	 * at construction time. This function also searches for the starting cell
	 * as the grid is read in.
	 *************************************************************************/

	public void read(BufferedReader in) throws IOException {
		for(int row = 0; row < rowCount(); row++) {
			String inputLine = in.readLine().trim();

			for(int column = 0; column < columnCount(); column++) {
				gridCells[row][column] = inputLine.charAt(column);

				if(gridCells[row][column] == 'X') {
					startX = column;
					startY = row;
				}
			}
		}
	}

	/**************************************************************************
	 * The solve function encapsulates the real recursive functions because
	 * it needs some extra parameters.  The starting state will be marked as
	 * reachable by the recursion. So this function also restores the starting
	 * grid cell as 'X'.
	 *************************************************************************/

	public void solve() {
		recursivelySolve(startX, startY, 'X');
		gridCells[startY][startX] = 'X';
	}

	/**************************************************************************
	 * The print function prints the grid to the screen in the same format
	 * that it is read in as.
	 *************************************************************************/

	public void print() {
		for(int row = 0; row < rowCount(); row++) {
			for(int column = 0; column < columnCount(); column++)
				System.out.print(gridCells[row][column]);
			System.out.println();
		}
	}

	/**************************************************************************
	 * rowCount is just a more readable form of accessing the bounds of the
	 * grid.
	 *************************************************************************/

	private int rowCount() {
		return gridCells.length;
	}

	/**************************************************************************
	 * likewise. assumes there is at least one row or this would crash.
	 *************************************************************************/

	private int columnCount() {
		return gridCells[0].length;
	}

	/**************************************************************************
	 * Here's the guts and glory...
	 * 
	 * So first we establish a basis whent here are no cells left to mark as
	 * reachable.  In this event, we either went off of the map, got to a
	 * wall, or went to a square that is already marked (prevents us from
	 * teleporting back and forth, or walking left/right/left/right, etc. If
	 * you are not convinced aobut this, considering reaching square 1,2 and
	 * then going everywhere you can from 1,2.  If you get to square 1,2 in
	 * the future, you know you already marked everything reachable from 1,2.
	 * So we can still clain that this is trivial.
	 * 
	 * We then keep track of the symbol that we see at this square (needed
	 * to check "?.!01923456789" movement.
	 * 
	 * The numberCheck function then looks at the symbol of the last square
	 * and the symbol of this square.  If we came from a number, it must have
	 * either a teleportation symbol or higher number.  This function returns
	 * true if there is a valid transition from the last square to this square.
	 * 
	 * Next we mark the current cell as visited.  This reduces the problem
	 * size for the recursive calls.  In effect, we always take off at least
	 * 1 square, so worst case, we have size * size recursive calls and then
	 * the recursion is trivial.
	 * 
	 * Next we check if the current symbol can teleport.  If it can, it moves
	 * to EVERY matching symbol on the map.
	 * 
	 * Finally we make the simplistic moves of up/down/left/right.  Again, we
	 * notify the function of the current symbol so it can verify numbers and
	 * such as it recurses.
	 *************************************************************************/

	private void recursivelySolve(int x, int y, char lastSymbol) {

		if(!validatePosition(x, y) || isWall(x, y) || alreadyVisited(x, y))
			return;

		char currentSymbol = gridCells[y][x];

		if(!numberCheck(lastSymbol, currentSymbol))
			return;

		gridCells[y][x] = 'R';

		if(canTeleport(currentSymbol))
			teleport(x, y, currentSymbol);

		recursivelySolve(x - 1, y, currentSymbol);
		recursivelySolve(x + 1, y, currentSymbol);
		recursivelySolve(x, y - 1, currentSymbol);
		recursivelySolve(x, y + 1, currentSymbol);
	}

	
	/**************************************************************************
	 * validatePosition returns true if the x,y position is inside the grid.
	 *************************************************************************/

	private boolean validatePosition(int x, int y) {
		return x >= 0 && x < columnCount() && y >= 0 && y < rowCount();
	}

	/**************************************************************************
	 * isWall returns true if the x,y position is a wall.  It assumes the
	 * position is validated prior to calling the function.
	 *************************************************************************/

	private boolean isWall(int x, int y) {
		return gridCells[y][x] == 'W';
	}

	/**************************************************************************
	 * alreadyVisited returns true if the x,y coordinate has already been
	 * reached.  This implies we have already marked everywhere that this
	 * square can legally get to.  Again, assume the x,y coordinate is already
	 * validated.
	 *************************************************************************/

	private boolean alreadyVisited(int x, int y) {
		return gridCells[y][x] == 'R';
	}

	/**************************************************************************
	 * canTeleport returns true if the symbol is a valid teleportation symbol.
	 *************************************************************************/

	private static boolean canTeleport(char symbol) {
		return teleportSymbols.indexOf(symbol) >= 0;
	}

	/**************************************************************************
	 * teleport makes the current symbol at location x,y teleport to every
	 * possible matching location.  It assumes the symbol is a valid teleport
	 * symbol.
	 *************************************************************************/

	private void teleport(int x, int y, char symbol) {
		for(int row = 0; row < rowCount(); row++)
			for(int column = 0; column < columnCount(); column++) {
				if(column == x && row == y)
					continue;

				if(symbol == gridCells[row][column])
					recursivelySolve(column, row, symbol);
			}
	}

	/**************************************************************************
	 * numberCheck returns true if the valid symbols make a valid transition
	 * from last to current given the rules of the problem.
	 * 
	 * This means:
	 * return true if last is not a digit
	 * return true if last is a digit and current is greater than or equal
	 * return false if last is a digit and current is less digit
	 * return false if last is a digit and current is a blank or wall
	 * return true if last is a digit and current is a teleporter
	 *************************************************************************/

	private static boolean numberCheck(char last, char current) {
		if(!Character.isDigit(last))
			return true;
		else if(Character.isDigit(current))
			return last <= current;
		else
			return canTeleport(current);
	}

	/**************************************************************************
	 * gridCells stores the state of each cell.
	 * 
	 * startX, startY store the starting location and are found in the read
	 * method.
	 *************************************************************************/

	private char [][]gridCells;
	private int startX, startY;

	/**************************************************************************
	 * teleportSymbols are the valid teleporter symbols;
	 * specialSymbols are the valid symbols for numberCheck
	 *************************************************************************/

	private static final String teleportSymbols = ".?!";
	private static final String specialSymbols = teleportSymbols + "0123456789";
}