Buscando la Salida - Problema 3 Preselectivo

buscandosalida.cpp

#include<iostream>
#include<queue>
using namespace std;

int mapa[1002][1002];

struct dato{
    int x;
    int y;
    int m;
};

void dereversa(int x,int y,int m){
    if(m>3){
        if(mapa[x+1][y]==m-1) dereversa(x+1,y,m-1);
        else if(mapa[x-1][y]==m-1) dereversa(x-1,y,m-1);
        else if(mapa[x][y+1]==m-1) dereversa(x,y+1,m-1);
        else if(mapa[x][y-1]==m-1) dereversa(x,y-1,m-1);
    }
    cout << x << ' ' << y << endl;
}

int main (){
	int N,M,i,j;
	cin >> N >> M;
	queue<dato> camino;
	dato aux,aux2;
	for(i=0;i<=N+1;i++){
        mapa[i][0]=0;
        mapa[i][M+1]=0;
	}
	for(i=0;i<=M+1;i++){
        mapa[0][i]=0;
        mapa[N+1][i]=0;
	}
	for(i=1;i<=N;i++) for(j=1;j<=M;j++){
        cin >> mapa[i][j];
	}
	mapa[1][1]=2;
	aux.x=1;
	aux.y=1;
	aux.m=2;
	camino.push(aux);
	while(!camino.empty()){
        aux=camino.front();
        if(!( aux.x==N&&aux.y==M ) ){
            aux2=aux;
            aux2.m++;
            if(mapa[aux.x+1][aux.y]==1){
                aux2.x++;
                mapa[aux2.x][aux2.y]=aux2.m;
                camino.push(aux2);
                aux2.x--;
            }
            if(mapa[aux.x-1][aux.y]==1){
                aux2.x--;
                mapa[aux2.x][aux2.y]=aux2.m;
                camino.push(aux2);
                aux2.x++;
            }
            if(mapa[aux.x][aux.y+1]==1){
                aux2.y++;
                mapa[aux2.x][aux2.y]=aux2.m;
                camino.push(aux2);
                aux2.y--;
            }
            if(mapa[aux.x][aux.y-1]==1){
                aux2.y--;
                mapa[aux2.x][aux2.y]=aux2.m;
                camino.push(aux2);
                aux2.y++;
            }
        }
        else break;
        camino.pop();
	}
	cout << aux.m-2 << endl;
    dereversa(N,M,aux.m);
	return 0;
}