#include #include #include using namespace std; struct cell { int x, y; int dis; cell*p; cell() {} cell(int i, int j, int dist,cell *par){ x=i; y=j; dis=dist; p=par; } }; bool isInside(int x, int y, int N) { if (x >=0 && x <= N-1 && y >= 0 && y <= N-1) return true; return false; } vector ans; void move(int i,int j,int ip,int jp) { if(ip-2==i && jp-1==j) ans.push_back("UL "); else if(ip-2==i && jp+1==j) ans.push_back("UR "); else if(ip==i && jp+2==j) ans.push_back("R "); else if(ip+2==i && jp+1==j) ans.push_back("LR "); else if(ip+2==i && jp-1==j) ans.push_back("LL "); else if(ip==i && jp-2==j) ans.push_back("L "); } void printShortestPath(int N,int i1,int j1,int i2,int j2) { int dx[] = {-2, -2, 0, 2, 2, 0}; int dy[] = {-1, 1, 2, 1, -1, -2}; queue q; cell* n=new cell(i1,j1, 0,NULL); q.push(n); cell* t; int x, y; bool **visit = new bool*[N]; for(int i = 0; i < N; i++) { visit[i] = new bool[N]; } for (int i = 0; i <= N-1; i++) for (int j = 0; j <= N-1; j++) visit[i][j] = false; visit[i1][j1] = true; while (!q.empty()) { t = q.front(); q.pop(); visit[t->x][t->y] = true; if (t->x == i2 && t->y == j2){ int ansd=t->dis; cout<dis<p!=NULL){ move(t->x,t->y,t->p->x,t->p->y); t=t->p; } for (int i=ansd-1;i>=0;i--){ cout<x + dx[i]; y = t->y + dy[i]; if (isInside(x, y, N) && !visit[x][y]){ n=new cell(x, y, t->dis + 1,t); q.push(n); } } } cout<<"Impossible"; return; } int main() { int n,i1,j1,i2,j2; cin>>n>>i1>>j1>>i2>>j2; printShortestPath(n,i1,j1,i2,j2); }