#include using namespace std; struct Pos{ int x; int y; Pos(int x, int y){ this->x = x; this->y = y; } }; struct KeepDist { int x; int y; int dist; vector moves; KeepDist(int x, int y, int d,vector moves){ this->x = x; this->y = y; this->dist = d; this->moves = moves; } KeepDist(int x, int y, int d){ this->x = x; this->y = y; this->dist = d; } }; struct Adj{ int x; int y; string move; Adj(int x, int y, string move){ this->x = x; this->y = y; this->move = move; } }; list adjacent(int x, int y, int n){ list adj; if(x>1 && y > 0) adj.push_back(Adj(x-2,y-1,"UL")); if(x>1 && y < n-1) adj.push_back(Adj(x-2,y+1,"UR")); if(y < n-2) adj.push_back(Adj(x,y+2,"R")); if(x< n-2 && y < n-1) adj.push_back(Adj(x+2,y+1,"LR")); if(x < n-2 && y > 0) adj.push_back(Adj(x+2,y-1,"LL")); if(y > 1) adj.push_back(Adj(x,y-2,"L")); return adj; } struct Answer{ int result; vector moves; Answer(int r, vector s){ this->result= r; this->moves = s; } Answer(int r){ this->result = r; } }; Answer ShortestPath(int n, int i1, int j1, int i2, int j2){ if(j2 == j1 && i2 == i1){ return Answer(0); } vector> visited(n,vector(n)); for(int i=0;i q; KeepDist s = KeepDist(i1,j1,0); visited[i1][j1] = true; q.push(s); while(!q.empty()){ KeepDist curr = q.front(); if(curr.x == i2 && curr.y == j2){ return Answer(curr.dist,curr.moves); } q.pop(); list adj = adjacent(curr.x, curr.y,n); for(auto i=adj.begin();i!=adj.end();i++){ if(!visited[(*i).x][(*i).y]){ visited[(*i).x][(*i).y] = true; curr.moves.push_back((*i).move); q.push(KeepDist((*i).x,(*i).y,curr.dist+1,curr.moves)); } } } return Answer(-1); } void printShortestPath(int n, int i1, int j1, int i2, int j2){ Answer ans = ShortestPath(n,i1,j1,i2,j2); if(ans.result==0) cout << 0 << endl; else if(ans.result==-1) cout << "Impossible" << endl; else{ cout << ans.result << endl; for(int i=0;i> n; int i_start; int j_start; int i_end; int j_end; cin >> i_start >> j_start >> i_end >> j_end; printShortestPath(n, i_start, j_start, i_end, j_end); return 0; }