#include #define mm 100000 using namespace std; string directions[] = {"UL", "UR", "R", "LR", "LL", "L"}; int col_offsets[] = {-1, 1, 2, 1, -1, -2}; int row_offsets[] = {-2, -2, 0, 2, 2, 0}; 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 > dist(n, vector(n,mm)); queue > to_explore; vector > prev(n, vector(n,7)); dist[i_start][j_start] = 0; to_explore.push(pair(i_start, j_start)); bool searching = true; while (!to_explore.empty() && searching){ pair pt = to_explore.front(); to_explore.pop(); int tmp_dist = dist[pt.first][pt.second] + 1; for (int i=0; i<6; ++i){ int row = pt.first + row_offsets[i]; int col = pt.second + col_offsets[i]; // check range: if (row < 0 || row >= n || col < 0 || col >=n) continue; // if not visited -> push to queue if (dist[row][col] == mm) { prev[row][col] = i; dist[row][col] = tmp_dist; if (pt.first == i_end && pt.second == j_end){ searching = false; break; } to_explore.push(pair(row,col)); } } } if (dist[i_end][j_end]==mm) { cout<<"Impossible\n"; } else { cout<< dist[i_end][j_end]<< endl; // backtrace stack moves; while (1){ int mv = prev[i_end][j_end]; moves.push(mv); i_end -= row_offsets[mv]; j_end -= col_offsets[mv]; if (i_end == i_start && j_end == j_start){ break; } } while (1){ int mv = moves.top(); moves.pop(); cout<< directions[mv]; if (moves.empty()){ cout<<"\n"; break; } else { cout<<" "; } } } } 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; }