/*
Lavirint je zapisan u datoteci "lavirint.dat" na sledeci nacin:
- u prvom redu zapisuju se praznim prostorom razdvojeni celi 
brojevi koji predstavljaju sirinu i visinu lavirinta;
- zatim sledi onoliko redova kolika je visina lavirinta, a u 
svakom redu po onoliko znakova kolika je sirina lavirinta;
- znak 'X' oznaka za zid, ' ' za put, 'O' za izlaz (ili cilj), 
a '@' za ulaz (ili pocetnu poziciju);
- mora postojati bar jedan ulaz i bar jedan izlaz.

Primer:
10 5
XXXXXXOXXX
X      X X
X XX XXX X
X        X
XXX@XXXXXX
Napisati program koji cita lavirint, proverava da li je ispravno 
zapisan, pronalazi najkraci put od ulaza do izlaza i prikazuje 
na standardonm izlazu najkraci put ucrtan u lavirint upotrebom 
znaka '.', kao u narednom primeru:

10 5
XXXXXXOXXX
X......X X
X.XXXXXX X
X.... X
XXXX@XXXXX
*/






#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

template <class T>
class Matrica
{
public:
	Matrica()
		{}

	Matrica( unsigned s, unsigned v, T t )
		: _podaci(s)
		{
		// proveru da su s i v > 0 ostavljamo za drugu priliku
		for( unsigned i=0; i<s; i++ ){
			// _podaci[i] = vector<T>(v);
			_podaci[i].resize(v);
			for( unsigned j=0; j<v; j++ )
				_podaci[i][j] = t;
			}
		}
	
	unsigned Sirina() const
		{ return _podaci.size(); }
	
	unsigned Visina() const
		{ return _podaci[0].size(); }
		
	vector<T>& operator[]( unsigned i )
		{ return _podaci[i]; }

	const vector<T>& operator[]( unsigned i ) const
		{ return _podaci[i]; }
	
private:
	vector< vector<T> > _podaci;
};

class Lavirint
{
public:
	class Pozicija {
		public:
			unsigned x,y;
			int prethodna;
			Pozicija( unsigned _x, unsigned _y, int _p )
				: x(_x), y(_y), prethodna(_p)
				{}				
	};
	
	Lavirint()
		: pronadjenPut(false)
		{}
	
	void PronalazenjePocetaka()
		{
		unsigned 
			s = _mapa.Sirina(),
			v = _mapa.Visina();
		for( unsigned i=0; i<v; i++ )
			for( unsigned j=0; j<s; j++ )
				if( _mapa[j][i] == '@' )
					putanja.push_back( Pozicija(j,i,-1) );
		}

	void PronalazenjeNajkracegPuta()
		{
		// pocinjemo trazenje
		putanja.clear();
		PronalazenjePocetaka();

		unsigned tekuca = 0;
		pronadjenPut = false;
		_obradjeno = Matrica<bool>( _mapa.Sirina(), _mapa.Visina(), false );
		
		// trazimo
		while( tekuca < putanja.size() && !pronadjenPut ){
			if( putanja[tekuca].y > 0 )
				proveraPolja( putanja[tekuca].x, putanja[tekuca].y-1, tekuca );
			if( putanja[tekuca].y < _mapa.Visina()-1 )
				proveraPolja( putanja[tekuca].x, putanja[tekuca].y+1, tekuca );
			if( putanja[tekuca].x > 0 )
				proveraPolja( putanja[tekuca].x-1, putanja[tekuca].y, tekuca );
			if( putanja[tekuca].x < _mapa.Sirina()-1 )
				proveraPolja( putanja[tekuca].x+1, putanja[tekuca].y, tekuca );
			tekuca++;
			}
			
		if( pronadjenPut )
			RestauracijaPutanje( tekuca-1 );
		}
	
	void RestauracijaPutanje( int poslednje )
		{
		_put = Matrica<bool>( _mapa.Sirina(), _mapa.Visina(), false );
		for( int i=poslednje; i>0; i=putanja[i].prethodna )
			_put[putanja[i].x][putanja[i].y] = true;
		}
		
	void proveraPolja( unsigned x, unsigned y, int prethodno )
		{
		if( _mapa[x][y] == 'O' ){
			pronadjenPut = true;
			}
		else if( _mapa[x][y] == ' ' && !_obradjeno[x][y] ){
			putanja.push_back( Pozicija(x,y,prethodno) );
			_obradjeno[x][y] = true;
			}
		}	
	
	void Citaj( istream& istr )
		{
		unsigned s,v;
		istr >> s >> v;
		_mapa = Matrica<char>( s, v, ' ' );
		for( unsigned i=0; i<v; i++ ){
			istr >> ws;
			for( unsigned j=0; j<s; j++ )
				_mapa[j][i] = istr.get();
			}
		}

	void Pisi( ostream& ostr ) const
		{
		unsigned 
			s = _mapa.Sirina(),
			v = _mapa.Visina();
		ostr << s << ' ' << v << endl;
		for( unsigned i=0; i<v; i++ ){
			for( unsigned j=0; j<s; j++ )
				if( pronadjenPut && _put[j][i] )
					ostr << '.';
				else 
					ostr << _mapa[j][i];
			ostr << endl;
			}
		}
		
private:
	Matrica<char> _mapa;
	Matrica<bool> _obradjeno;
	Matrica<bool> _put;	
	vector<Pozicija> putanja;
	unsigned xPocetka, yPocetka;
	bool pronadjenPut;
};

istream& operator >> ( istream& istr, Lavirint& l )
{
	l.Citaj(istr);
	return istr;
}

ostream& operator << ( ostream& ostr, const Lavirint& l )
{
	l.Pisi(ostr);
	return ostr;
}

main()
{
	Lavirint l;
	ifstream f("lavirint.dat");
	f >> l;
	l.PronalazenjeNajkracegPuta();
	cout << l;
	return 0;
}
