#include #include #include #include #include #include using namespace std; typedef pair position_t; inline bool isPositionOnBoard(position_t p, int n) { return (p.first >= 0 && p.first < n && p.second >= 0 && p.second < n); } void validBackMoves(position_t p, int n, vector>& results) { static vector> offsets = // ordered by increasing prio { { 0, -2}, // L { 2, -1}, // LL { 2, 1}, // LR { 0, 2}, // R { -2, 1}, // UR { -2, -1} // UL }; for (int i = 0; i < offsets.size(); i++) { position_t t = { p.first - offsets[i].first, p.second - offsets[i].second}; if (isPositionOnBoard(t, n)) results.push_back({t, i}); } } int main() { int n; cin >> n; int si, sj, di, dj; cin >> si >> sj >> di >> dj; vector >>> dists(n); for (int i = 0; i < n; i++) dists[i].resize(n, {-1, {{0,0}, 0}}); queue qu; dists[di][dj] = make_pair(0, make_pair(make_pair(0,0), 0)); qu.push({di, dj}); while (qu.size()) { position_t p = qu.front(); qu.pop(); vector> backMoves; validBackMoves(p, n, backMoves); for (int i = 0; i < backMoves.size(); i++) { position_t const t = backMoves[i].first; int const prio = backMoves[i].second; if (-1 == dists[t.first][t.second].first) qu.push(t); if ((-1 != dists[t.first][t.second].first) && ((dists[t.first][t.second].first < dists[p.first][p.second].first + 1) || (dists[t.first][t.second].second.second > prio))) continue; dists[t.first][t.second].first = dists[p.first][p.second].first + 1; dists[t.first][t.second].second = make_pair(p, prio); } } if (-1 == dists[si][sj].first) cout << "Impossible" << endl; else { cout << dists[si][sj].first << endl; static string directions[] = { "L", "LL", "LR", "R", "UR", "UL" }; for (position_t p { si, sj}; (p.first != di) || (p.second != dj); p = dists[p.first][p.second].second.first) { cout << directions[dists[p.first][p.second].second.second] << " "; } cout << endl; } return 0; }