#include #include #include #include using namespace std; constexpr int kMaxN = 300, kInf = 0x3f3f3f3f; constexpr int kDir[6][2] = {{-2, 0}, {-1, -2}, {1, -2}, {2, 0}, {-1, +2}, {+1, +2}}; const string kMoves[6] = {"L", "UL", "UR", "R", "LL", "LR"}; constexpr int order[6] = {1, 2, 3, 5, 4, 0}; int min_dist[kMaxN][kMaxN], from[kMaxN][kMaxN]; int main() { memset(min_dist, 0x3f, sizeof min_dist); int n, x0, y0, x1, y1; cin >> n >> x0 >> y0 >> x1 >> y1; min_dist[x0][y0] = 0; queue> bfq; bfq.emplace(x0, y0); while (not bfq.empty()) { const auto node = bfq.front(); bfq.pop(); for (int i = 0; i < 6; i += 1) { int x = node.first + kDir[order[i]][1]; int y = node.second + kDir[order[i]][0]; if (x >= n or y >= n or x < 0 or y < 0 or min_dist[x][y] <= 1 + min_dist[node.first][node.second]) { continue; } min_dist[x][y] = 1 + min_dist[node.first][node.second]; from[x][y] = order[i]; bfq.emplace(x, y); } } if (min_dist[x1][y1] == kInf) { cout << "Impossible\n"; } else { cout << min_dist[x1][y1] << '\n'; vector moves; while (x1 != x0 or y1 != y0) { moves.push_back(from[x1][y1]); int x = x1 - kDir[from[x1][y1]][1]; int y = y1 - kDir[from[x1][y1]][0]; x1 = x; y1 = y; } reverse(moves.begin(), moves.end()); for (auto&& move : moves) { cout << kMoves[move] << ' '; } cout << '\n'; } }