#include #include #include #include #include #include using point = std::pair; inline bool operator==(const point& p1, const point& p2) { return p1.first == p2.first && p1.second == p2.second; } inline point operator+(const point& p1, const point& p2) { return std::make_pair(p1.first + p2.first, p1.second + p2.second); } int main() { std::ios::sync_with_stdio(false); auto color = [](const point& p)->bool{return (p.first & 1) == (p.second & 1); }; size_t n; point start, end; std::cin >> n >> start.first >> start.second >> end.first >> end.second; std::vector moves = { { -2, -1 }, { -2, 1 }, { 0, 2 }, { 2, 1 }, { 2, -1 }, { 0, -2 } }; std::vector> visited(n, std::vector(n, 0)); auto valid = [n, &visited](const point& p)->bool{ return p.first >= 0 && p.first < n && p.second >= 0 && p.second < n && visited[p.first][p.second] == 0; }; using position = std::pair>; auto print = [](const position& p) { std::vector moves_str = { "UL", "UR", "R", "LR", "LL", "L" }; // UL, UR, R, LR, LL, L std::cout << p.second.size() << std::endl; for (auto x : p.second) { std::cout << moves_str[x] << " "; } std::cout << std::endl; }; std::queue state; bool found = false; state.push(std::make_pair(start, std::vector())); while (!state.empty()) { const auto ¤t = state.front(); for (int i = 0; i < moves.size(); ++i) { point p = current.first + moves[i]; if (valid(p)) { visited[p.first][p.second] = 1; position pn = make_pair(p, current.second); pn.second.push_back(i); if (p == end) { print(pn); found = true; break; } state.push(pn); } } state.pop(); if (found) break; } if (!found) std::cout << "Impossible\n"; return 0; }