import java.util.ArrayList;
import java.util.List;

public class Maze {
	private static char[][] oldMaze;
	private static char[][] newMaze;
	private static int nrows;
	private static int ncols;
	private static List<Point> path = new ArrayList<Point>();

	public static void main(String[] args) {
		String[] strings = {
			"XXXXXXXXXXXXXXXXXXXXXXXX",
			"XXXXXX.XXXXXXXX.......BX", //A is start, B is end
			"XA.XXX........X.XXXXXXXX",
			"XX.XXX.XXXXXXXX.XXX.XXXX",
			"XX.......XX.........XXXX",
			"XXXXXXXX.XX.XXX.XXX.XXXX",
			"XXXX.XXX.XX.XXX.XXX.XXXX",
			"XXXX...........XXXX.XXXX",
			"XXXXXXXXXXXXXXXXXX..XXXX",
			"XXXXXXXXXXXXXXXXXXXXXXXX"
		};
		nrows = strings.length;
		ncols = strings[0].length();
		int arow = -1;   //position of the starting point
		int acol = -1;

		oldMaze = new char[nrows][ncols];

		for (int row = 0; row < nrows; ++row) {
			for (int col = 0; col < ncols; ++col) {
				oldMaze[row][col] = strings[row].charAt(col);
				if (oldMaze[row][col] == 'A') {
					arow = row;
					acol = col;
				}
			}
		}

		assert arow >= 0 && acol >= 0;   //We found the starting point.

		//Create a copy of the oldMaze.
		newMaze = new char[nrows][]; 
		for(int row = 0; row < nrows; ++row) {
			newMaze[row] = oldMaze[row].clone();
		}

		if (findPath(arow, acol)) {
			printPath();
			System.exit(0);
		}
		System.exit(1);
	}

	/*
	Return true if the newMaze has a path starting at point (row, col),
	and ending at point B.
	*/
	private static boolean findPath(int row, int col) {
		if (newMaze[row][col] == 'X') {
			//Our path is blocked right at the very beginning.
			return false;
		}

		path.add(new Point(row, col));   //tentative

		//Is the job already done?

		if (row < nrows - 1 && newMaze[row + 1][col] == 'B') {
			path.add(new Point(row + 1, col));
			return true;
		}

		if (row > 0 && newMaze[row - 1][col] == 'B') {
			path.add(new Point(row - 1, col));
			return true;
		}

		if (col < ncols - 1 && newMaze[row][col + 1] == 'B') {
			path.add(new Point(row, col + 1));
			return true;
		}

		if (col > 0 && newMaze[row][col - 1] == 'B') {
			path.add(new Point(row, col - 1));
			return true;
		}

		newMaze[row][col] = 'X'; //Make sure we don't come back this way.

		if (
			   row < nrows - 1 && findPath(row + 1, col)
			|| row > 0         && findPath(row - 1, col)
			|| col < ncols - 1 && findPath(row,     col + 1)
			|| col > 0         && findPath(row,     col - 1)
		) {
			return true;
		}

		path.remove(path.size() - 1);   //It was only tentative.
		return false;
	}

	private static void printPath() {
		//Print the path into the oldMaze.
		for (Point point: path) {
			int row = point.row;
			int col = point.col;
			if (oldMaze[row][col] != 'A' && oldMaze[row][col] != 'B') {
				oldMaze[row][col] = '+';
			}
		}

		//Display the oldMaze.
		for (int row = 0; row < nrows; ++row) {
			for (int col = 0; col < ncols; ++col) {
				System.out.print(oldMaze[row][col]);
			}
			System.out.println();
		}
	}
}

//The path from A to B is stored as a List of Points.

class Point {
	public int row;
	public int col;

	Point(int row, int col) {
		this.row = row;
		this.col = col;
	}

	public String toString() {
		return "(" + row + ", " + col + ")";
	}
}