#include #include #include #include #include #include #include #include #include #include using namespace std; int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int n, istart, jstart, iend, jend; cin >> n >> istart >> jstart >> iend >> jend; queue< pair > frontier; pair start (istart, jstart); frontier.push(start); map< pair, pair > came_from; came_from[start] = start; pair goal(iend, jend); while(!frontier.empty()){ pair current = frontier.front(); frontier.pop(); if(current == goal){ break; } //UL, UR, R, LR, LL, L queue> neighbours; int uli = current.first - 2; int ulj = current.second - 1; if(uli >= 0 && ulj >= 0){ neighbours.push(pair(uli,ulj)); } int uri = current.first - 2; int urj = current.second + 1; if(uri >= 0 && urj < n){ neighbours.push(pair(uri,urj)); } int ri = current.first; int rj = current.second + 2; if(rj < n){ neighbours.push(pair(ri, rj)); } int lri = current.first + 2; int lrj = current.second + 1; if(lrj < n && lri < n){ neighbours.push(pair(lri,lrj)); } int lli = current.first + 2; int llj = current.second - 1; if(llj > 0 && lli < n){ neighbours.push(pair(lli,llj)); } int li = current.first; int lj = current.second - 2; if( lj >= 0){ neighbours.push(pair(li, lj)); } int chi = 0; int chj = 0; int min_dist = INT_MAX; while(!neighbours.empty()){ pair next = neighbours.front(); neighbours.pop(); if(came_from.find(next) == came_from.end()){ int priority = abs(goal.first - next.first) + abs(goal.second - next.second); if( min_dist > priority){ min_dist = priority; chi = next.first; chj = next.second; } came_from[next] = current; } } if( current == pair(chi,chj)){ break; } frontier.push(pair(chi, chj)); } if(came_from.find(goal) == came_from.end()){ cout << "Impossible" << endl; } else { stack< pair> v; pair pa = goal; do{ v.push(pa); pa = came_from[pa]; }while(pa != start); pa = start; cout << v.size() << endl; queue path; string pathstr = ""; do{ pair pc = v.top(); v.pop(); //UL, UR, R, LR, LL, L if(pa.first - 2 == pc.first && pa.second - 1 == pc.second){ path.push("UL"); pathstr += "UL "; } else if(pa.first - 2 == pc.first && pa.second + 1 == pc.second) { path.push("UR"); pathstr += "UR "; } else if(pa.first == pc.first && pa.second + 2 == pc.second){ path.push("R"); pathstr += "R "; } else if(pa.first + 2 == pc.first && pa.second + 1 == pc.second ){ path.push("LR"); pathstr += "LR "; } else if(pa.first + 2 == pc.first && pa.second - 1 == pc.second){ path.push("LL"); pathstr += "LL "; } else if(pa.first == pc.first && pa.second - 2 == pc.second){ path.push("L"); pathstr += "L "; } pa = pc; }while(!v.empty()); cout << pathstr << endl; } return 0; }