#include using namespace std; class Entry { public: int value; Entry *next; }; class Stack { Entry *head; public: Stack(void) { head = NULL; } void push(int value) { Entry *entry = new Entry; entry->value = value; entry->next = head; head = entry; } int pop(void) { Entry *del = head; if ( head ) { int ret; head = head->next; ret = del->value; delete del; return ret; } return -1; } bool isEmpty(void) { if ( head ) return false; else return true; } }; bool valid(int i, int j, int n) { if ( i < 0 || j < 0 ) return false; if ( i >= n || j >= n ) return false; return true; } #define IDX(i,j) (((i)<<8) | (j)) #define ROW(idx) ((idx)>>8) #define COL(idx) ((idx)&0xFF) int colMove[] = { -1, 1, 2, 1, -1, -2 }; int rowMove[] = { -2, -2, 0, 2, 2, 0 }; const char *STR[] = { "LR", "LL", "L" , "UL", "UR", "R" }; const int order[] = { 3, 4, 5, 0, 1, 2 }; void printShortestPath(int n, int i_end, int j_end, int i_start, int j_start) { int i, j; int *cost = new int[n<<8]; int *prev = new int[n<<8]; Stack st; for ( i = 0 ; i < (n<<8) ; i++ ) cost[i] = prev[i] = -1; int sidx = IDX(i_start, j_start); int eidx = IDX(i_end, j_end); st.push(sidx); cost[sidx] = 0; while (!st.isEmpty()) { int idx = st.pop(); int ncost = cost[idx] + 1; // if ( idx == eidx ) // break; for ( i = 0 ; i < 6 ; i++ ) { int nr, nc; nr = ROW(idx) + rowMove[i]; nc = COL(idx) + colMove[i]; if ( !valid(nr,nc, n) ) continue; int nidx = IDX(nr,nc); if ( cost[nidx] == -1 || cost[nidx] > ncost ) { cost[nidx] = ncost; prev[nidx] = i; st.push(nidx); } else if ( cost[nidx] == ncost && order[prev[nidx]] > order[i] ) { prev[nidx] = i; } } } #if 0 for ( i = 0 ; i < n ; i++ ) { for ( j = 0 ; j < n ; j++ ) { cout << cost[IDX(i,j)] << " "; } cout << endl; } cout << endl; cout << endl; for ( i = 0 ; i < n ; i++ ) { for ( j = 0 ; j < n ; j++ ) { cout << prev[IDX(i,j)] << " "; } cout << endl; } #endif if ( cost[eidx] < 0 ) { cout << "Impossible" << endl; return; } string str; cout << cost[eidx] << endl; i = i_end, j = j_end; while ( i != i_start || j != j_start ) { int idx = IDX(i,j); int dir = prev[idx]; cout << STR[dir] << " "; str = string(STR[dir]) + " " + str; i = i - rowMove[dir]; j = j - colMove[dir]; } // cout << str << endl; } int main() { int n; cin >> 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; }