#include #include #include #include #include #include #include struct Jump { int i; int j; int s; }; int dist_estimate(int from_i, int from_j, int to_i, int to_j, std::vector< std::vector >& board) { // return abs(from_i - to_i) + abs(from_j - to_j); return board[from_i][from_j]; } bool inside_grid(int n, int i, int j) { if (0 <= i && i < n && 0 <= j && j < n) { return true; } return false; } bool try_move(int n, int from_i, int from_j, int to_i, int to_j, int& next_i, int& next_j, int& min_estimate, std::vector< std::vector >& board) { if (inside_grid(n, from_i, from_j)) { int curr_estimate = dist_estimate(from_i, from_j, to_i, to_j, board); if (curr_estimate < min_estimate && curr_estimate != -1) { min_estimate = curr_estimate; next_i = from_i; next_j = from_j; return true; } } return false; } int next_move(int n, int from_i, int from_j, int to_i, int to_j, int& next_i, int& next_j, std::vector< std::vector >& board) { int min_estimate = 3*n; // 3x as max int nm; if (try_move(n, from_i-2, from_j-1, to_i, to_j, next_i, next_j, min_estimate, board)) { nm = 0; } if (try_move(n, from_i-2, from_j+1, to_i, to_j, next_i, next_j, min_estimate, board)) { nm = 1; } if (try_move(n, from_i, from_j+2, to_i, to_j, next_i, next_j, min_estimate, board)) { nm = 2; } if (try_move(n, from_i+2, from_j+1, to_i, to_j, next_i, next_j, min_estimate, board)) { nm = 3; } if (try_move(n, from_i+2, from_j-1, to_i, to_j, next_i, next_j, min_estimate, board)) { nm = 4; } if (try_move(n, from_i, from_j-2, to_i, to_j, next_i, next_j, min_estimate, board)) { nm = 5; } return nm; } void compute_path(int n, int from_i, int from_j, int to_i, int to_j, std::vector& path, std::vector< std::vector >& board) { while (from_i != to_i || from_j != to_j) { path.push_back(next_move(n, from_i, from_j, to_i, to_j, from_i, from_j, board)); } return; } void reach_to(int n, int i, int j, int s, std::queue< Jump >& next, std::vector< std::vector >& board) { if (inside_grid(n, i, j) && board[i][j] == -1) { Jump current; current.i = i; current.j = j; current.s = s; next.push(current); board[i][j] = s; } return; } void mark_reachable(int from_i, int from_j, std::vector< std::vector >& board) { int n = board.size(); std::queue next; Jump current; current.i = from_i; current.j = from_j; current.s = 0; next.push(current); board[current.i][current.j] = 0; while (!next.empty()) { current = next.front(); next.pop(); reach_to(n, current.i-2, current.j-1, current.s+1, next, board); reach_to(n, current.i-2, current.j+1, current.s+1, next, board); reach_to(n, current.i, current.j+2, current.s+1, next, board); reach_to(n, current.i+2, current.j+1, current.s+1, next, board); reach_to(n, current.i+2, current.j-1, current.s+1, next, board); reach_to(n, current.i, current.j-2, current.s+1, next, board); } return; } int main() { int n; std::cin >> n; int from_i, from_j, to_i, to_j; std::cin >> from_i >> from_j >> to_i >> to_j; std::vector< std::vector > board(n, std::vector(n, -1)); mark_reachable(from_i, from_j, board); if (board[to_i][to_j] == -1) { std::cout << "Impossible" << std::endl; return 0; } for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { board[i][j] = -1; } } mark_reachable(to_i, to_j, board); std::vector path; compute_path(n, from_i, from_j, to_i, to_j, path, board); int plen = path.size(); std::cout << plen << std::endl; for(int i = 0; i < plen; ++i) { if (path[i] == 0) { std::cout << "UL"; if (i < plen-1) { std::cout << ' '; } } if (path[i] == 1) { std::cout << "UR"; if (i < plen-1) { std::cout << ' '; } } if (path[i] == 2) { std::cout << "R"; if (i < plen-1) { std::cout << ' '; } } if (path[i] == 3) { std::cout << "LR"; if (i < plen-1) { std::cout << ' '; } } if (path[i] == 4) { std::cout << "LL"; if (i < plen-1) { std::cout << ' '; } } if (path[i] == 5) { std::cout << "L"; if (i < plen-1) { std::cout << ' '; } } } std::cout << std::endl; return 0; }