#include #define UL 0 #define UR 1 #define R 2 #define LR 3 #define LL 4 #define L 5 using namespace std; const int INF = 1e9 + 9, MAXN = 200; const string priority[6] = {"UL", "UR", "R", "LR", "LL", "L"}; int n, minDist[MAXN][MAXN], parent[MAXN][MAXN]; pairstartPos, endPos; queue >q; vectormoves; pair next(paircur, string id){ if (id[0] == 'U' && id[1] == 'L'){ cur.first += 2; cur.second += 1; } else if (id[0] == 'U' && id[1] == 'R'){ cur.first += 2; cur.second -= 1; } else if (id[0] == 'R'){ cur.second -= 2; } else if (id[0] == 'L' && id[1] == 'R'){ cur.first -= 2; cur.second -= 1; } else if (id[0] == 'L' && id[1] == 'L'){ cur.first -= 2; cur.second += 1; } else if (id[0] == 'L'){ cur.second += 2; } return cur; } int main(){ //freopen ("input.txt", "r", stdin); //freopen ("output.txt", "w", stdout); scanf ("%d", &n); scanf ("%d%d%d%d", &startPos.first, &startPos.second, &endPos.first, &endPos.second); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++){ minDist[i][j] = INF; parent[i][j] = -1; } minDist[startPos.first][startPos.second] = 0; q.push({startPos.first, startPos.second}); while (!q.empty()){ int i = q.front().first; int j = q.front().second; q.pop(); if (i-2 >= 0 && j-1 >= 0 && minDist[i-2][j-1] > minDist[i][j] + 1){ minDist[i-2][j-1] = minDist[i][j] + 1; parent[i-2][j-1] = UL; q.push({i-2, j-1}); } if (i-2 >= 0 && j+1 < n && minDist[i-2][j+1] > minDist[i][j] + 1){ minDist[i-2][j+1] = minDist[i][j] + 1; parent[i-2][j+1] = UR; q.push({i-2, j+1}); } if (j+2 < n && minDist[i][j+2] > minDist[i][j] + 1){ minDist[i][j+2] = minDist[i][j] + 1; parent[i][j+2] = R; q.push({i, j+2}); } if (i+2 < n && j+1 < n && minDist[i+2][j+1] > minDist[i][j] + 1){ minDist[i+2][j+1] = minDist[i][j] + 1; parent[i+2][j+1] = LR; q.push({i+2, j+1}); } if (i+2 < n && j-1 >= 0 && minDist[i+2][j-1] > minDist[i][j] + 1){ minDist[i+2][j-1] = minDist[i][j] + 1; parent[i+2][j-1] = LL; q.push({i+2, j-1}); } if (j-2 >= 0 && minDist[i][j-2] > minDist[i][j] + 1){ minDist[i][j-2] = minDist[i][j] + 1; parent[i][j-2] = L; q.push({i, j-2}); } } int cnt = minDist[endPos.first][endPos.second]; if (cnt == INF){ printf ("Impossible"); return 0; } printf ("%d\n", cnt); /*for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++) printf ("%d ", parent[i][j]); printf ("\n"); }*/ int action = parent[endPos.first][endPos.second]; pairnextCell; nextCell = {endPos.first, endPos.second}; while (cnt--){ //cout << priority[action] << " "; moves.push_back(priority[action]); nextCell = next(nextCell, priority[action]); //printf ("%d %d\n", nextCell.first, nextCell.second); action = parent[nextCell.first][nextCell.second]; } reverse(moves.begin(), moves.end()); for (int i = 0; i < moves.size(); i++) cout<< moves[i] << " "; return 0; }