/*
 * labyrinth.cpp
 *
 *  Created on: 14.01.2014
 *      Author: trifon
 */

#include <iostream>
using namespace std;

const int MAX = 100;
char L[MAX][MAX];
int width, height;

void readLabyrinth() {
	cin >> width >> height;
	// трябва да прескочим един нов ред
	cin.getline(L[0],1);
	for(int i = 0; i < height; i++)
		cin.getline(L[i], width + 1);
}

void printLabyrinth() {
	for(int i = 0 ; i < height; i++)
		cout << L[i] << endl;
}

void findStartingPoint(int& x, int& y) {
	for(x = 0; x < height; x++)
		for(y = 0; y < width; y++)
			if (L[x][y] == '^')
				return;
}

/**
 * Търсим съкровището, започвайки от (x,y)
 * Връща дали е намерено съкровище
 */
bool findTreasure(int x, int y, int step) {
	//cout << "Опит да стъпим на (" << x << ',' << y << ')' << endl;
	//printLabyrinth();
	// лесен лош случай
	if (x < 0 || y < 0 || x >= height || y >= width ||
		L[x][y] == '#' || L[x][y] == '.' ||
		L[x][y] >= '0' && L[x][y] <= '9') {
		return false;
	}
	// Сигурни сме, че не сме излезли извън матрицата
	// лесен добър случай
	if (L[x][y] == '$') {
		cout << "Намерихме съкровището! На позиция (";
		cout << x << ',' << y << ')' << endl;
		cout << "За " << step << " стъпки" << endl;
		printLabyrinth();
		return false;
	}
	L[x][y] = step % 10 + '0';
	bool result =
		   findTreasure(x - 1, y, step + 1) || // нагоре
		   findTreasure(x + 1, y, step + 1) || // надолу
		   findTreasure(x, y - 1, step + 1) || // наляво
		   findTreasure(x, y + 1, step + 1);   // надясно
	if (!result)
		L[x][y] = '.';
	return result;
}

/**
 * Търсим съкровището, започвайки от (x,y)
 * Намира всички възможни пътища до съкровището
 */
void findTreasureAll(int x, int y, int step) {
	//cout << "Опит да стъпим на (" << x << ',' << y << ')' << endl;
	//printLabyrinth();
	// лесен лош случай
	if (x < 0 || y < 0 || x >= height || y >= width ||
		L[x][y] == '#' || L[x][y] == '.' ||
		L[x][y] >= '0' && L[x][y] <= '9') {
		return;
	}
	// Сигурни сме, че не сме излезли извън матрицата
	// лесен добър случай
	if (L[x][y] == '$') {
		cout << "Намерихме съкровището! На позиция (";
		cout << x << ',' << y << ')' << endl;
		cout << "За " << step << " стъпки" << endl;
		printLabyrinth();
		return;
	}
	L[x][y] = step % 10 + '0';
	findTreasureAll(x - 1, y, step + 1); // нагоре
	findTreasureAll(x + 1, y, step + 1); // надолу
	findTreasureAll(x, y - 1, step + 1); // наляво
	findTreasureAll(x, y + 1, step + 1);   // надясно
	L[x][y] = ' ';
	return;
}

int main() {
	readLabyrinth();
	printLabyrinth();
	int x, y;
	findStartingPoint(x, y);
	cout << "Започваме от (" << x << ',' << y << ')' << endl;
	cout << findTreasure(x, y, 1);
}