#include #include #include #include using namespace std; // Movimientos realizables bool valid(int i,int j,int n) { if( 0<=i && idI,arraydJ, vector< vector >&movs, vector< vector >&used ) { int w,wI,wJ,aux,auxI,auxJ; queuetoSearch; toSearch.push(one); while( !answerFlag && !toSearch.empty() ) { w = toSearch.front(); toSearch.pop(); wI = w/n; wJ = w%n; for(int i=0;i<6;++i) { auxI = wI+dI[i]; auxJ = wJ+dJ[i]; if( valid(auxI,auxJ,n) && used[auxI][auxJ]==0 ) { movs[auxI][auxJ] = i; used[auxI][auxJ] = 1; aux = auxI*n + auxJ; if( aux==two ) answerFlag = true; toSearch.push(aux); } } } } int main() { // Tamano del tablero int n; cin >> n; // Estado incial y objetivo int ii1,jj1,ii2,jj2; cin >> ii1 >> jj1; cin >> ii2 >> jj2; static int one = ii1*n + jj1; static int two = ii2*n + jj2; // Declarar auxiliares arraydI = {-2,-2,0,2, 2, 0}; arraydJ = {-1, 1,2,1,-1,-2}; vector< vector >movs(n,vector(n,0)); movs[ii1][jj1] = -1; vector< vector >used(n,vector(n,0)); used[ii1][jj1] = 1; // Busqueda bool answerFlag = false; printShortestPath(one,two,answerFlag,n,dI,dJ,movs,used); // Respuesta if( answerFlag ) { int wI,wJ,minimum = 0; stackrebuild; wI = ii2; wJ = jj2; while( movs[wI][wJ]!=-1 ) { switch( movs[wI][wJ] ) { case(0): wI+=2; wJ+=1; rebuild.push("UL"); break; case(1): wI+=2; wJ-=1; rebuild.push("UR"); break; case(2): wJ-=2; rebuild.push("R" ); break; case(3): wI-=2; wJ-=1; rebuild.push("LR"); break; case(4): wI-=2; wJ+=1; rebuild.push("LL"); break; case(5): wJ+=2; rebuild.push("L" ); } ++minimum; } cout << minimum << endl; while( !rebuild.empty() ) { cout << rebuild.top() << " "; rebuild.pop(); } } else { cout << "Impossible" << endl; } return 0; }