#include using namespace std; stack> local_stack; bool check_valid(int x, int y, int n) { if (x < n && y < n && x >= 0 && y >= 0) return true; else return false; } int x_val[6] = { -2, -2,0,2,2,0 }; int y_val[6] = { -1, 1, 2,1,-1,-2 }; string val[6] = { "UL","UR", "R", "LR","LL", "L"}; void count_Steps(vector>&visited, vector< vector> &result, int n, vector< vector> &update_position) { int i_start; int j_start; if (local_stack.empty()) { return; } pair result1 = local_stack.top(); local_stack.pop(); i_start = result1.first; j_start = result1.second; if (visited[i_start][j_start] == 0) { visited[i_start][j_start] = 1; for (int i = 0; i < 6; i++) { int loc_i = i_start + x_val[i]; int loc_j = j_start + y_val[i]; if (check_valid(loc_i, loc_j, n)) { if (result[i_start][j_start] + 1 < result[loc_i][loc_j]) { result[loc_i][loc_j] = min(result[i_start][j_start] + 1, result[loc_i][loc_j]); update_position[loc_i][loc_j] = val[i] + " " + update_position[i_start][j_start]; } local_stack.push(make_pair(loc_i, loc_j)); } } } count_Steps(visited, result, n, update_position); } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { // Print the distance along with the sequence of moves. vector> visited(n, vector(n, 0)); vector> result(n, vector(n, INT_MAX)); vector> update_position(n, vector(n)); result[i_start][j_start] = 0; update_position[i_start][j_start] = "\0"; local_stack.push(make_pair(i_start, j_start)); count_Steps(visited, result, n, update_position); if (result[i_end][j_end] == INT_MAX) cout << "Impossible" << endl; else { cout << result[i_end][j_end] << endl; cout << update_position[i_end][j_end] << 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; }