#include #define s second #define f first using namespace std; ifstream fin("Cin.txt"); vector dirx = {-1, 1, 2, 1, -1, -2}; vector diry = {-2, -2, 0, 2, 2, 0}; vector mov_names = {"UL", "UR", "R", "LR", "LL", "L"}; int MAXN = 205; int N; vector > field(MAXN, vector(MAXN, -1)); vector > visited(MAXN, vector(MAXN)); vector > > history(MAXN, vector >(MAXN, vector(0))); bool on_board(int x, int y) { if (0 <= x && x < N && 0 <= y && y < N) { return 1; } return 0; } void dfs(int x0, int y0) { field[y0][x0] = 0; priority_queue, pair > > , vector< pair, pair > > >, greater< pair, pair > > > > Q; Q.push({0, {{}, {x0, y0}}}); while (!Q.empty()) { auto cur = Q.top(); Q.pop(); int x = cur.s.s.f; int y = cur.s.s.s; if (visited[y][x]) { continue; } int dist = cur.f; vector hist = cur.s.f; //cout << x << " " << y << " " << dist << "\n"; visited[y][x] = 1; history[y][x] = hist; field[y][x] = dist; for (int dir = 0; dir < 6; dir++) { int posx = x + dirx[dir]; int posy = y + diry[dir]; if (on_board(posx, posy) && !visited[posy][posx]) { auto hist1 = hist; hist1.push_back(dir); Q.push({dist + 1, {hist1, {posx, posy}}}); } } } } int main() { cin >> N; int x0, y0, x1, y1; cin >> y0 >> x0 >> y1 >> x1; dfs(x0, y0); if (field[y1][x1] == -1) { cout << "Impossible\n"; return 0; } /*if (!((y1 % 4 == y0 % 4 && x0 % 2 == x1 % 2) || (y1 % 4 == (y0 + 6) % 4 && x0 % 2 != x1 % 2))) { cout << "Impossible\n"; return 0; }*/ cout << field[y1][x1] << "\n"; for (auto i : history[y1][x1]) { cout << mov_names[i] << " "; } }