#include "plosinovka.hpp"

string soubor = ""; // Absolutni cesta ke vstupnimu souboru

int main (int argc, char **args) {
	load();	
	inic();

	// Chci vypsat cestu
	if (bfs()) {
		write_path();		
	}

	return 0;
}

void write_path() {
	int curri, currj;
	curri = endv.first;
	currj = endv.second;
	Prev tmp;
	ostream_iterator<int> outit (std::cout," ");

		while (true) {			
			
			out.push_back(make_pair( make_pair(curri , currj), make_pair(prevv[curri][currj].key, prevv[curri][currj].state) ));

			
			if (curri == startv.first && currj == startv.second) {
				break;
			}
			tmp = prevv[curri][currj];
			curri = tmp.i;
			currj = tmp.j;
		}

		out.pop_back();

		int curr_key, curr_move;
		int posi, posj;
		bool path = false;
		bool end_bra = false;
		for (vector<pair<pair<int, int>, pair<int, int>> >::reverse_iterator idx = out.rbegin(); idx < out.rend(); idx++) {
			posi = idx->first.first;
			posj = idx->first.second;

			curr_move = idx->second.first;
			curr_key = idx->second.second;
			if (curr_key == 0 && !path) {
				std::cout << curr_move << " ";
			} else if (path && hra[posi+1][posj] == '#') {
				
				std::cout << curr_move << ") ";
				path = false;
			} else if (curr_key != 0 && !path) {
				path = true;
				std::cout << "J(" << curr_move << " ";				
			} else if (curr_key != 0 && path) {
				path = true;
				std::cout << " " << curr_move << " ";				
			}
			
			
		}
		if (path) {
			std::cout << ")" << endl;
		}

		cout << endl;
}

void move( int npi, int npj, Node x, int key) {
	Node curr(npi, npj, x.state, x.sec + 1, x.i, x.j, key);
	char newpos;
	newpos = hra[npi][npj];
	
	if (newpos != '#' && newpos != '@' && !used[npi][npj] && !inq[npi][npj]) {			

		// Ted musim doskocit
		if (x.state == 2) {
			int k = npi;
			while (true) {
				// Doskocil jsem
				if (hra[k+1][npj] == '#') {
					curr.state = 4; 
					npi = k;
					curr.i = k;
					if (!used[npi][npj] && !inq[npi][npj]) {
						inq[k][npj] = true;					
						q.push (curr);
					}

					break;
				// Propadnul jsem se
				} else if (hra[k+1][npj] == '@') {					
					break;
				}

				k++;
			}			
		} else {
			int k = npi;
			// Jsem na pevne zemi
			if (hra[k+1][npj] == '#') {
				if (x.state == 1) {
					curr.state = 3; 
				} else {
					curr.state = 0;
				}
				
				inq[k][npj] = true;
				q.push (curr);
			} else {
				// Budiz to skok
				curr.state = x.state + 1;
				inq[k][npj] = true;
				q.push (curr);

				// Padam
				k++;
				while (true) {
					// Dopadnul jsem
					if (hra[k+1][npj] == '#') {
						if (x.state == 1) {
							curr.state = 3; 
						} else {
							curr.state = 0;
						}

						npi = k;
						curr.i = k;
						if (!used[npi][npj] && !inq[npi][npj]) {
							inq[k][npj] = true;					
							q.push (curr);
						}
						break;
					// Propadnul jsem se
					} else if (hra[k+1][npj] == '@') {					
						break;
					}

					k++;
				}		
			}
		}
	}
}

void add_neigh(Node & x) {	
	if (x.state > 2) x.state = 0; // Abych na ceste poznal, ze skakal
	
	// move 1	
	move (x.i+1, x.j-1, x, 1);
	// move 2
	if (hra[x.i+1][x.j] != '.' && hra[x.i+1][x.j] != '@') {
		move (x.i+1, x.j, x, 2);
	}
	// move 3
	move (x.i+1, x.j+1, x, 3);
	// move 4
	move (x.i, x.j-1, x, 4);
	// move 6
	move (x.i, x.j+1, x, 6);
	// move 7
	move (x.i-1, x.j-1, x, 7);
	// move 8
	move (x.i-1, x.j, x, 8);
	// move 9
	move (x.i-1, x.j+1, x, 9);
}

bool bfs() {
	Node curr, tmp;	
	inq[startv.first][startv.second] = true;
	q.push(Node(startv.first, startv.second, 0, 0, 0, 0, 0));
	
	while (!q.empty()) {
		curr = q.front();
		q.pop();
		inq[curr.i][curr.j] = false;
		

		if (curr.i == endv.first && curr.j == endv.second) {
			prevv[curr.i][curr.j] = Prev(curr.previ, curr.prevj, curr.state, curr.key);
			cout << curr.sec << " sekund" << endl;
			return true;
		}

		if (!used[curr.i][curr.j]) {
			prevv[curr.i][curr.j] = Prev(curr.previ, curr.prevj, curr.state, curr.key);
			used[curr.i][curr.j] = true;
			add_neigh(curr);
		}

	}

	cout << "Matfyzak je navzdy ztraceny." << endl;
	return false;
}


void inic() {
	used.resize (n2, vector< bool> (m2, false));
	inq.resize (n2, vector< bool> (m2, false));
	prevv.resize(n2, vector< Prev> (m2));	
}

void load() {
	file.open(soubor, ios::in);
	
	file >> n >> m;
	n2= n+2;
	m2 = m+2;
	
	string buffer(m2, '#');

	hra.push_back(buffer);
	for (int i=0; i<n; i++) {
		file >> buffer;
		buffer.insert(buffer.begin(), '#');
		buffer.push_back('#');
		hra.push_back(buffer);	
	}
	string b2(m2, '@');
	
	hra.push_back(b2);
	hra.push_back(b2);
	
	file.close();
	
	for (int i =0; i<n2; i++) {
		cout << hra[i] << endl;
		for (int j=0; j<m2; j++) {
			if (hra[i][j] == 'M') {
				startv = make_pair(i, j);
			} 
			if (hra[i][j] == 'V') {
				endv = make_pair(i, j);
			}
			
		}		
	}
}