#include #include #include #include #include #include #include struct node{ int i; int j; struct node * next; }; struct node * head; struct node * tail; int empty(){ return head==NULL; } void enqueue(int i,int j){ if(head==NULL) { head = malloc(sizeof(struct node)); head->i = i; head->j = j; head->next = NULL; tail = head; return; } tail->next = malloc(sizeof(struct node)); tail = tail->next; tail->i = i; tail->j = j; tail->next = NULL; return; } struct node * dequeue(){ struct node * temp = head; head = head->next; return temp; } int dist[200][200]; int path[200][200]; void visit(int i,int j,int p,int d){ dist[i][j] = d+1; path[i][j] = p; enqueue(i,j); } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { dist[i_start][j_start] = 0; enqueue(i_start,j_start); while(!empty() && dist[i_end][j_end]==-1){ struct node * pos = dequeue(); int i = pos->i,j = pos->j; int d = dist[i][j]; if(i-2>=0 && j-1>=0 && dist[i-2][j-1]==-1){ visit(i-2,j-1,1,d); } if(i-2>=0 && j+1=0 && dist[i+2][j-1]==-1){ visit(i+2,j-1,5,d); } if(j-2>=0 && dist[i][j-2]==-1){ visit(i,j-2,6,d); } } if(dist[i_end][j_end]==-1){ printf("Impossible"); } else{ printf("%d\n",dist[i_end][j_end]); int i=i_end,j = j_end; int ar[200]; int ar_size = 0; while(i!=i_start || j!=j_start){ ar[ar_size++]=path[i][j]; switch(path[i][j]){ case 1: i+=2; j+=1; break; case 2: i+=2; j-=1; break; case 3: j-=2; break; case 4: i-=2; j-=1; break; case 5: i-=2; j+=1; break; case 6: j+=2; break; } } for(int a=ar_size-1;a>=0;a--){ switch(ar[a]){ case 1: printf("UL "); break; case 2: printf("UR "); break; case 3: printf("R "); break; case 4: printf("LR "); break; case 5: printf("LL "); break; case 6: printf("L "); break; } } } } int main() { int n; scanf("%i", &n); int i_start; int j_start; int i_end; int j_end; scanf("%i %i %i %i", &i_start, &j_start, &i_end, &j_end); for(int i=0;i