#include using namespace std; 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. int grid[200][200]; fill(&grid[0][0], &grid[0][0]+200*200, -1); queue> myQ; int currLevel = 1; int nextLevel = 0; int levelCount = 0; myQ.push(make_pair(i_start, j_start)); while(!myQ.empty()) { pair pos = myQ.front(); myQ.pop(); if (pos.first == i_end && pos.second == j_end){ break; } //UL - 1 if (pos.first-2>=0 && pos.second-1>=0 && grid[pos.first-2][pos.second-1]==-1){ myQ.push(make_pair(pos.first-2, pos.second-1)); grid[pos.first-2][pos.second-1] = 1; nextLevel++; } //UR - 2 if (pos.first-2>=0 && pos.second+1=0 && grid[pos.first+2][pos.second-1]==-1){ myQ.push(make_pair(pos.first+2, pos.second-1)); grid[pos.first+2][pos.second-1] = 5; nextLevel++; } //L - 6 if (pos.second-2>=0 && grid[pos.first][pos.second-2]==-1){ myQ.push(make_pair(pos.first, pos.second-2)); grid[pos.first][pos.second-2] = 6; nextLevel++; } currLevel--; if (currLevel == 0){ currLevel = nextLevel; nextLevel = 0; levelCount++; } } if (grid[i_end][j_end]==-1){ cout << "Impossible" << endl; }else { cout << levelCount< steps; int i = i_end; int j = j_end; while(i!=i_start || j!=j_start){ switch(grid[i][j]){ case 1: steps.push_back("UL"); i+=2; j+=1; break; case 2: steps.push_back("UR"); i+=2; j-=1; break; case 3: steps.push_back("R"); j-=2; break; case 4: steps.push_back("LR"); i-=2; j-=1; break; case 5: steps.push_back("LL"); i-=2; j+=1; break; case 6: steps.push_back("L"); j+=2; break; default: break; } } for (int s=steps.size()-1; s>=0; s--){ cout << steps[s]; if (s>0) cout << ' '; } 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; }