#include #include #include #include #include #include #include #include enum class path_type { EMPTY, ROOT, UL, UR, R, LR, LL, L }; struct parent_t { path_type path = path_type::EMPTY; int parent_i, parent_j; }; int main() { int n; std::cin >> n; int i_start; int j_start; int i_end; int j_end; std::cin >> i_start >> j_start >> i_end >> j_end; std::vector board(n * n); std::deque> queue; queue.emplace_back(i_start, j_start, -1, -1, path_type::ROOT); while (!queue.empty()) { int i, j, pi, pj; path_type path; std::tie(i, j, pi, pj, path) = queue.front(); queue.pop_front(); if (i < 0 || i >= n || j < 0 || j >= n) { continue; } if (board[i * n + j].path != path_type::EMPTY) { continue; } board[i * n + j].path = path; board[i * n + j].parent_i = pi; board[i * n + j].parent_j = pj; queue.emplace_back(i - 2, j - 1, i, j, path_type::UL); // UL queue.emplace_back(i - 2, j + 1, i, j, path_type::UR); // UR queue.emplace_back(i, j + 2, i, j, path_type::R); // R queue.emplace_back(i + 2, j + 1, i, j, path_type::LR); // LR queue.emplace_back(i + 2, j - 1, i, j, path_type::LL); // LL queue.emplace_back(i, j - 2, i, j, path_type::L); // L if (i == i_end && j == j_end) { break; } } const parent_t* current = &board[i_end * n + j_end]; if (current->path == path_type::EMPTY) { std::cout << "Impossible" << std::endl; return 0; } std::vector result; while (current->path != path_type::ROOT) { switch (current->path) { case path_type::UL: result.emplace_back("UL"); break; case path_type::UR: result.emplace_back("UR"); break; case path_type::R: result.emplace_back("R"); break; case path_type::LR: result.emplace_back("LR"); break; case path_type::LL: result.emplace_back("LL"); break; case path_type::L: result.emplace_back("L"); break; } current = &board[current->parent_i * n + current->parent_j]; } std::cout << result.size() << std::endl; for (int i = result.size()-1; i >= 0; --i) { if (i != result.size()-1) { std::cout << ' '; } std::cout << result[i]; } std::cout << std::endl; return 0; }