#include <stdio.h>
#include "queue.h"

int main(int argc,char *argv[]) {
    FILE *in;
    int m,n,i,j,mozese;
    char polje[100][101];
    int put[100][100]; // Ovo ce nam pamtiti put do Slavice.

    queue q;
    
    // Malo je bedasto sta je tip podataka pozicija definiran
    // u queue.h, al nema veze.
    pozicija x,y,t;
    
    pozicija okolo[]={ {-1,0},{1,0},{0,-1},{0,1} };
    
    if (argc<2) {
	printf("Nije napisano ime ulazne datoteke!\n");
	return 1;
    }

    if ((in=fopen(argv[1],"r"))==NULL) {
	printf("Grjeska prilikom otvaranja datoteke!\n");
	return 1;
    }

    // Ucitavamo dimenzije i labirint
    fscanf(in,"%d%d",&m,&n);
    for (i=0;i<m;i++) {
	fscanf(in,"%s",polje[i]);
	// Usput u labirintu trazimo X i Y i postavljamo put[i][j] na -1.
	for (j=0;j<n;j++) {
	    if (polje[i][j]=='X') {
		x.i=i;
		x.j=j;
	    }
	    else if (polje[i][j]=='Y') {
		y.i=i;
		y.j=j;
	    }
	    put[i][j]=-1;
	}
    }

    // Inicijaliziramo queue i stavljamo 'Slavka' na njega.
    make_null(&q);
    enqueue(x,&q);

    // mozese postavljamo na 0, sto znaci da se zasad ne moze od
    // Slavka do Slavice.
    mozese=0;

    // Izvrsavamo BFS, trazimo dok ne nadjemo Slavicu.
    while (!empty(q)) {
	t=front(q);
	dequeue(&q);

	// Gledamo jesmo nasli Slavicu. Ne mozemo direktno usporedit
	// t i y tako da napisemo t==y.
	if (t.i==y.i && t.j==y.j) {
	    // Nadjosmo put od Slavka do Slavice. Sto se dalje dogodilo
	    // u labirintu ostavljamo masti citatelja koda na volju.
	    mozese=1;
	    break;
	}
	
	// Razmakom oznacavamo pozicije koje su provjerene. Zasto razmakom?
	// Super ce nam labirint izgledati kad iscrtamo put, ubijamo 2 muhe
	// jednim udarcem. :)
	polje[t.i][t.j]=' ';
	
	// Ako su neprovjerene, stavljamo gornju, donju, lijevu i desnu
	// poziciju na queue. Koristimo trik. :)
	for (i=0;i<4;i++) {
	    t.i+=okolo[i].i;
	    t.j+=okolo[i].j;
	    if (polje[t.i][t.j]!='#' && polje[t.i][t.j]!=' ') {
		enqueue(t,&q);
		// Usput pamtimo kako bi dosli do pozicije koju smo upravo
		// stavili na queue.
		put[t.i][t.j]=i;
	    }
	    t.i-=okolo[i].i;
	    t.j-=okolo[i].j;
	}
    }

    printf("Slavko %s doci do Slavice.\n",(mozese==1?"moze":"ne moze"));

    // Ako postoji put, krecemo od Slavice unatrag. Postavljamo tockice
    // i gledamo s kojeg smo polja dosli na trenutno. Primijetimo da nam
    // je nakon izlaska iz gornje petlje t==y.
    if (mozese==1) {
	// Obrisemo tockice koje nisu bile obrisane tokom BFS-a.
	for (i=0;i<m;i++)
	    for (j=0;j<n;j++)
		if (polje[i][j]=='.') polje[i][j]=' ';
	
	while (t.i!=x.i || t.j!=x.j) { // Dakle, dok ne dodjemo opet do Slavka...
	    // Gledamo koji je ono bio okolo[] koji nas je doveo do pozicije t.
	    i=okolo[put[t.i][t.j]].i;
	    j=okolo[put[t.i][t.j]].j;
	    // Oduzimamo taj okolo od trenutne pozicije da bi se doveli korak
	    // unatrag.
	    t.i-=i;
	    t.j-=j;
	    // Ako smo dosli do Slavka, stavimo X, inace tockicu.
	    // (Ti znakovi su bili obrisani razmacima.)
	    if (t.i==x.i && t.j==x.j) polje[t.i][t.j]='X';
	    else polje[t.i][t.j]='.';
	}

	// Ispisujemo novi labirint. Red po red, da skratimo posao.
	for (i=0;i<m;i++)
	    printf("%s\n",polje[i]);
    }

    fclose(in);

    return 0;
}