#include #include #include #include #include #include #include #include using namespace std; int dx[6] = {-1, 1, 2, 1, -1, -2}; int dy[6] = {-2, -2, 0, 2, 2, 0}; bool isOut(int i, int j, int n){ return i < 0 || i >= n || j < 0 || j >= n; } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { // Print the distance along with the sequence of moves. vector> v(n, vector(n, -1)); vector>> v2(n, vector>(n)); v[i_start][j_start] = 0; v2[i_start][j_start] = vector(); queue> que; que.push(make_pair(i_start, j_start)); while(!que.empty()){ pair p = que.front(); que.pop(); int i = p.first; int j = p.second; int cnt = v[i][j]; vector vv = v2[i][j]; for(int k=0; k<6; k++){ int y = i + dy[k]; int x = j + dx[k]; if(isOut(y, x, n)) continue; if(v[y][x] != -1) continue; v[y][x] = cnt + 1; vv.push_back(k); v2[y][x] = vv; vv.pop_back(); que.push(make_pair(y, x)); } } if(v[i_end][j_end] == -1){ cout << "Impossible" << endl; return; } cout << v[i_end][j_end] << endl; vector vvv = v2[i_end][j_end]; sort(vvv.begin(), vvv.end()); vector s = {"UL", "UR", "R", "LR", "LL", "L"}; for(auto i : vvv) cout << s[i] << " "; cout << endl; } 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; }