#include #include #include #include #include #include #include #include using namespace std; int main() { int n, istart, jstart, iend, jend; cin >> n >> istart >> jstart >> iend >> jend; vector< vector > prev_move(n, vector(n, -1)); vector< vector > filled(n, vector(n, false) ); vector< vector> > prev(n, vector >(n,{-1,-1}) ); deque> q; q.push_back({istart,jstart}); vector> moves = { {-2,-1}, {-2,1}, {0,2}, {2,1}, {2,-1}, {0,-2} }; while(!q.empty()){ pair current = q.front(); //cout << "pos: " << current.first << ", " << current.second << endl; // if(filled[current.first][current.second]){ //already filled // continue; // } filled[current.first][current.second] = true; //make moves int move_index = 0; bool exitearly = false; for(auto i: moves){ int inew = current.first + i.first; int jnew = current.second + i.second; if((inew >=0) && (inew < n) && (jnew >= 0) && (jnew < n)){ if(!filled[inew][jnew]){ //cout << "filled: " << inew << ", " << jnew << endl; filled[inew][jnew] = true; assert(current.first!=-1); assert(current.second!=-1); prev[inew][jnew] = { current.first, current.second }; prev_move[inew][jnew] = move_index; if(inew==iend && jnew==jend){ exitearly = true; break; } q.push_back({inew,jnew}); } } ++move_index; } q.pop_front(); if(exitearly){ break; } } /*cout << "backtrack: " << endl; for(auto & i : prev){ for(auto j : i){ cout << "{" << j.first << "," << j.second << "} "; } cout << endl; }*/ vector final_moves; if(!filled[iend][jend]){ cout << "Impossible" << endl; return 0; }else{ prev[istart][jstart] = {istart,jstart}; int ibacktrack = iend; int jbacktrack = jend; //cout << "start: " << istart << ", " << jstart << endl; //cout << "bt: " << ibacktrack << ", " << jbacktrack << endl; while( true ){ assert(ibacktrack!=-1); assert(jbacktrack!=-1); if(ibacktrack == istart && jbacktrack == jstart){ break; } final_moves.push_back(prev_move[ibacktrack][jbacktrack]); pair temp = prev[ibacktrack][jbacktrack]; ibacktrack = temp.first; jbacktrack = temp.second; //cout << "bt: " << ibacktrack << ", " << jbacktrack << endl; } } std::reverse(final_moves.begin(),final_moves.end()); cout << final_moves.size() << endl; for(auto i : final_moves ){ if(i == 0){ cout << "UL "; } else if(i == 1){ cout << "UR "; } else if(i == 2){ cout << "R "; } else if(i == 3){ cout << "LR "; } else if(i == 4){ cout << "LL "; } else if(i == 5){ cout << "L "; } else{ assert(false); } } cout << endl; return 0; }