public class Dijkstra {
	//Each cell is either ...
	enum State {
		WALL,
		DONE,
		NOTDONE
	};
		
	//Each cell has four neighbors.
	static final Offset[] offsets = {
		new Offset( 1,  0), //below the current cell
		new Offset(-1,  0), //above
		new Offset( 0,  1), //right
		new Offset( 0, -1)  //leftt
	};

	int nrows;
	int ncols;
	Cell[][] board;

	public static void main(String[] args) {
		String[] strings = {
			"XXXXXXX",
			"XA....X",   //The starting point is A.
			"X.X.XXX",
			"X...X.X",
			"XXXXXXX"
		};

		Dijkstra dijkstra = new Dijkstra(strings);
		System.out.println(dijkstra);
		System.exit(0);
	}

	Dijkstra(String[] strings) {
		int arow = -1;   //position of the starting point
		int acol = -1;

		nrows = strings.length;
		ncols = strings[0].length();
		board = new Cell[nrows][ncols];

		//Create the board.

		for (int row = 0; row < nrows; ++row) {
			for (int col = 0; col < ncols; ++col) {
				char c = strings[row].charAt(col);
				State state = c == 'X' ? State.WALL : State.NOTDONE;
				board[row][col] = new Cell(state);
				if (c == 'A') {
					arow = row;
					acol = col;
				}
			}
		}

		//The starting point is at distance 0 from itself.
		assert arow != -1 && acol != -1;
		board[arow][acol].distance = 0;

		//Initialize the current location to the starting point.
		int crow = arow;
		int ccol = acol;

		for (;;) {
			Cell current = board[crow][ccol];
			current.state = State.DONE;

			//Reach out to the four neighbors of the current cell.
			for (Offset offset: offsets) {
				int row = crow + offset.drow;
				int col = ccol + offset.dcol;
				if (0 <= row && row < nrows
					&& 0 <= col && col < ncols) {
					Cell neighbor = board[row][col];
					if (neighbor.state == State.NOTDONE) {
						int newDistance = current.distance + 1;
						if (newDistance < neighbor.distance) {
							neighbor.distance = newDistance;
						}
					}
				}
			}

			if (allAreDone() || inaccessible()) {
				break;
			}

			Coordinates coordinates = closestNotDone();
			crow = coordinates.row;
			ccol = coordinates.col;
		}
	}

	//Return true if all cells are done.

	private boolean allAreDone() {
		for (int row = 0; row < nrows; ++row) {
			for (int col = 0; col < ncols; ++col) {
				if (board[row][col].state == State.NOTDONE) {
					return false;
				}
			}
		}

		return true;
	}

	//Return the coordinates of the not done cell that is closest to the
	//starting point.  (Or if there are several that are tied,
	//return the coordinates of one of them).

	private Coordinates closestNotDone() {
		int minDistance = Integer.MAX_VALUE;
		int mrow = -1;
		int mcol = -1;

		for (int row = 0; row < nrows; ++row) {
			for (int col = 0; col < ncols; ++col) {
				Cell cell = board[row][col];
				if (cell.state == State.NOTDONE
					&& cell.distance < minDistance) {
					minDistance = cell.distance;
					mrow = row;
					mcol = col;
				}
			}
		}

		assert mrow != -1 && mcol != -1;
		return new Coordinates(mrow, mcol);
	}

	//Return true if the board has at least one cell that is
	//inaccessible from the starting point.

	private boolean inaccessible() {
		for (int row = 0; row < nrows; ++row) {
			for (int col = 0; col < ncols; ++col) {
				Cell cell = board[row][col];
				if (cell.state == State.NOTDONE && cell.distance < Integer.MAX_VALUE) {
					//Further progess is possible.
					return false;
				}
			}
		}

		//Further progress is impossible.
		return true;
	}

	public String toString() {
		String s = "";
		for (int row = 0; row < nrows; ++row) {
			for (int col = 0; col < ncols; ++col) {
				Cell cell = board[row][col];
				switch (cell.state) {
				case WALL:
					s += "XX ";
					break;
				default:
					int distance = cell.distance;
					distance = Math.min(distance, 99);
					s += String.format("%02d ", distance);
				}
			}

			if (row < nrows - 1) {
				s += "\n\n";
			}
		}
		return s;
	}
}


class Cell {
	public Dijkstra.State state;
	public int distance;

	Cell(Dijkstra.State state) {
		this.state = state;
		this.distance = Integer.MAX_VALUE;
	}

	public String toString() {
		return "(" + state + ", " + distance + ")";
	}
}

class Coordinates {
	public int row;   //Fields must be non-negative.
	public int col;

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

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

class Offset {
	public int drow;   //Fields could be positive or negative.
	public int dcol;

	Offset(int drow, int dcol) {
		this.drow = drow;
		this.dcol = dcol;
	}

	public String toString() {
		return "(" + drow + ", " + dcol + ")";
	}
}