#include using namespace std; #define DEBUG 1 // Direction priorities: UL, UR, R, LR, LL, L. enum e_direction { UL = 0, UR, R, LR, LL, L }; const string direction_names[] = { "UL", "UR", "R", "LR", "LL", "L" }; const int max_directions = 6; const int max_size = 200; const int direction_j_change[max_directions] = { -1, 1, 2, 1, -1, -2 }; const int direction_i_change[max_directions] = { -2, -2, 0, 2, 2, 0 }; int discovered[max_size][max_size]; const int undiscovered_mark = -1; void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { for (int i = 0; i < max_size; ++i) { for (int j = 0; j < max_size; ++j) { discovered[i][j] = undiscovered_mark; } } queue< pair > q; q.push(make_pair(i_start, j_start)); while (!q.empty()) { pair curr_node = q.front(); int curr_i = curr_node.first; int curr_j = curr_node.second; q.pop(); for (int dir_i = 0; dir_i < max_directions; ++dir_i) { int new_i = curr_i + direction_i_change[dir_i]; int new_j = curr_j + direction_j_change[dir_i]; if (new_i < 0 || new_i >= n || new_j < 0 || new_j >= n) { continue; } if (discovered[new_i][new_j] == (int)undiscovered_mark) { discovered[new_i][new_j] = dir_i; q.push(make_pair(new_i, new_j)); } } } if (discovered[i_end][j_end] != undiscovered_mark) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cerr << discovered[i][j] << " "; } cerr << endl; } stack directions; int curr_i = i_end; int curr_j = j_end; do { int dir = discovered[curr_i][curr_j]; assert(dir != undiscovered_mark); directions.push(dir); curr_i -= direction_i_change[dir]; curr_j -= direction_j_change[dir]; } while (curr_i != i_start || curr_j != j_start); cout << directions.size() << endl; while (!directions.empty()) { int dir = directions.top(); directions.pop(); cout << direction_names[dir] << " "; } } else { cout << "Impossible"; } 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; }