#include using namespace std; void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { int** tabel = new int*[n]; for(int i = 0; i < n; i++) { tabel[i] = new int[n]; for(int j = 0; j < n; j++) { tabel[i][j] = -1; } } tabel[i_end][j_end] = 0; queue > q; q.push(make_pair(i_end, j_end)); while(!q.empty()) { pair pii = q.front(); q.pop(); int ci = pii.first; int cj = pii.second; if(ci - 2 >= 0) { if(cj - 1 >= 0 && tabel[ci - 2][cj - 1] == -1) { tabel[ci - 2][cj - 1] = tabel[ci][cj] + 1; q.push(make_pair(ci - 2, cj - 1)); } if(cj + 1 < n && tabel[ci - 2][cj + 1] == -1) { tabel[ci - 2][cj + 1] = tabel[ci][cj] + 1; q.push(make_pair(ci - 2, cj + 1)); } } if(ci + 2 < n) { if(cj - 1 >= 0 && tabel[ci + 2][cj - 1] == -1) { tabel[ci + 2][cj - 1] = tabel[ci][cj] + 1; q.push(make_pair(ci + 2, cj - 1)); } if(cj + 1 < n && tabel[ci + 2][cj + 1] == -1) { tabel[ci + 2][cj + 1] = tabel[ci][cj] + 1; q.push(make_pair(ci + 2, cj + 1)); } } if(cj - 2 >= 0 && tabel[ci][cj - 2] == -1) { tabel[ci][cj - 2] = tabel[ci][cj] + 1; q.push(make_pair(ci, cj - 2)); } if(cj + 2 < n && tabel[ci][cj + 2] == -1) { tabel[ci][cj + 2] = tabel[ci][cj] + 1; q.push(make_pair(ci, cj + 2)); } } if(tabel[i_start][j_start] == -1) { cout << "Impossible" << endl; return; } cout << tabel[i_start][j_start] << endl; int pi = i_start; int pj = j_start; while(tabel[pi][pj] > 0) { if(i_start != pi || j_start != pj) { cout << " "; } if(pi - 2 >= 0) { if(pj - 1 >= 0 && tabel[pi - 2][pj - 1] < tabel[pi][pj]) { cout << "UL"; pi -= 2; pj--; continue; } if(pj + 1 < n && tabel[pi - 2][pj + 1] < tabel[pi][pj]) { cout << "UR"; pi -= 2; pj++; continue; } } if(pj + 2 < n && tabel[pi][pj + 2] < tabel[pi][pj]) { cout << "R"; pj += 2; continue; } if(pi + 2 < n) { if(pj + 1 < n && tabel[pi + 2][pj + 1] < tabel[pi][pj]) { cout << "LR"; pi += 2; pj++; continue; } if(pj - 1 >= 0 && tabel[pi + 2][pj - 1] < tabel[pi][pj]) { cout << "LL"; pi += 2; pj--; continue; } } if(pj - 2 >= 0 && tabel[pi][pj - 2] < tabel[pi][pj]) { cout << "L"; pj -= 2; continue; } } cout << 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; }