#include #include #include #include #include #include #define MAXN 200 using namespace std; struct Field { int dist = -1; int i_prev = -1; int j_prev = -1; Field () {} Field (int _dist, int _i_prev, int _j_prev) { dist = _dist; i_prev = _i_prev; j_prev = _j_prev; } }; Field mat[MAXN][MAXN]; int r[] = {-2, -2, 0, 2, 2, 0}; int s[] = {-1, 1, 2, 1, -1, -2}; queue > Q; bool check(int n, int i, int j) { return (i >= 0 && i < n) && (j >= 0 && j < n) && (mat[i][j].dist == -1); } string get_jump(int i_to, int j_to, int i_from, int j_from) { for (int i = 0; i < 6; ++i) { if (i_to == i_from + r[i] && j_to == j_from + s[i]) { switch (i) { case 0: return "UL"; case 1: return "UR"; case 2: return "R"; case 3: return "LR"; case 4: return "LL"; case 5: return "L"; } } } return ""; } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { mat[i_start][j_start] = Field(0, i_start, j_start); Q.push(make_pair(i_start, j_start)); while (!Q.empty()) { int curr_x = Q.front().first; int curr_y = Q.front().second; Q.pop(); for (int i = 0; i < 6; ++i) { int tmp_x = curr_x + r[i]; int tmp_y = curr_y + s[i]; if (check(n, tmp_x, tmp_y)) { Q.push(make_pair(tmp_x, tmp_y)); mat[tmp_x][tmp_y] = Field(mat[curr_x][curr_y].dist + 1, curr_x, curr_y); } } } if (mat[i_end][j_end].dist != -1) { cout << mat[i_end][j_end].dist << "\n"; int to_i = i_end; int to_j = j_end; vector path; while (to_i != i_start || to_j != j_start) { int from_i = mat[to_i][to_j].i_prev; int from_j = mat[to_i][to_j].j_prev; path.push_back(get_jump(to_i, to_j, from_i, from_j)); to_i = from_i; to_j = from_j; } reverse(path.begin(), path.end()); for (int i = 0; i < path.size(); ++i) { cout << path[i] << " "; } } else { cout << "Impossible\n"; } } int main() { int n; cin >> n; int i_start; int j_start; int i_end; int j_end; cin >> i_start >> j_start >> i_end >> j_end; printShortestPath(n, i_start, j_start, i_end, j_end); return 0; }