#include using namespace std; void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { int dy = i_end-i_start; int dx = j_end-j_start; int adx = abs(dx); int ady = abs(dy); int sdx = (dx >= 0)?1:-1; int sdy = (dy >= 0)?1:-1; int res = 0; stringstream ss; //cout << dx << " " << dy << endl; if (ady%2 == 1) { cout << "Impossible" <0?adx+(dy_steps - adx)/2:dy_steps; int cnt2= dy_steps-cnt; int p = j_start; int d = sdx; res += cnt+cnt2; //cout << cnt << " " << cnt2 << endl; if (d == -1) { // increasing x while (cnt > 0) { if (p - 1 >= 0 && cnt > 0) { p -=1; ss << "UL "; cnt--; } else { p+=1; ss << "UR "; cnt2--; } } while (cnt2 > 0) { p+=1; ss << "UR "; cnt2--; } } else { while (cnt > 0) { if (p - 1 >= 0 && cnt2 > 0) { p -=1; ss << "UL "; cnt2--; } else { p+=1; ss << "UR "; cnt--; } } while (cnt2 > 0) { p-=1; ss << "UL "; cnt2--; } } } int dx_steps = (adx-dy_steps)/2; if (dx > 0 && dx_steps>0) { for (int i = 0; i < dx_steps; i++) { ss << "R "; } res+=dx_steps; } // do dy_steps if (dy > 0) { // downwards int cnt = (dy_steps - adx)>0?adx+(dy_steps - adx)/2:dy_steps; int cnt2= dy_steps-cnt; int p = j_start; int d = sdx; res += cnt+cnt2; if (d == 1) { // increasing x while (cnt > 0) { if (p + 1 >= 0 && cnt > 0) { p +=1; ss << "LR "; cnt--; } else { p-=1; ss << "LL "; cnt2--; } } while (cnt2 > 0) { p-=1; ss << "LL "; cnt2--; } } else { while (cnt > 0) { if (p + 1 >= 0 && cnt2 > 0) { p +=1; ss << "LR "; cnt2--; } else { p-=1; ss << "LL "; cnt--; } } while (cnt2 > 0) { p+=1; ss << "LR "; cnt2--; } } } if (dx < 0 && dx_steps>0) { for (int i = 0; i < dx_steps; i++) { ss << "L "; } res+=dx_steps; } cout << res <> 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; }