#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. swap(i_start,j_start); swap(i_end,j_end); bool vis[n][n]; fill(vis[0],vis[0]+n*n,false); int dist[n][n],x,y; fill(dist[0],dist[0]+n*n,1000000); int mov[n][n]; fill(mov[0],mov[0]+n*n,-1); queue > Q; Q.push({i_start,j_start}); dist[i_start][j_start] = 0; mov[i_start][j_start] = 0; while(!Q.empty()){ x = Q.front().first; y = Q.front().second; Q.pop(); if(x==i_end && y==j_end) break; if(vis[x][y]) continue; vis[x][y] = true; if(x-1>=0 && y-2>=0) { if(dist[x-1][y-2]>dist[x][y]+1) dist[x-1][y-2]=dist[x][y]+1,mov[x-1][y-2] = 1,Q.push({x-1,y-2}); } if(x+1=0) { if(dist[x+1][y-2]>dist[x][y]+1) dist[x+1][y-2]=dist[x][y]+1,mov[x+1][y-2] = 2,Q.push({x+1,y-2}); } if(x+2dist[x][y]+1) dist[x+2][y]=dist[x][y]+1,mov[x+2][y] = 3,Q.push({x+2,y}); } if(x+1dist[x][y]+1) dist[x+1][y+2]=dist[x][y]+1,mov[x+1][y+2] = 4,Q.push({x+1,y+2}); } if(x-1>=0 && y+2dist[x][y]+1) dist[x-1][y+2]=dist[x][y]+1,mov[x-1][y+2] = 5,Q.push({x-1,y+2}); } if(x-2>=0) { if(dist[x-2][y]>dist[x][y]+1) dist[x-2][y]=dist[x][y]+1,mov[x-2][y] = 6,Q.push({x-2,y}); } } if(dist[i_end][j_end]==1000000) cout<<"Impossible\n"; else { cout< S; while(i_start!=i_end || j_start!=j_end) { if(mov[i_end][j_end]==1) { S.push("UL"); i_end +=1; j_end +=2; } else if(mov[i_end][j_end]==2) { S.push("UR"); i_end -=1; j_end +=2; } else if(mov[i_end][j_end]==3) { S.push("R"); i_end -=2; } else if(mov[i_end][j_end]==4) { S.push("LR"); i_end -=1; j_end -=2; } else if(mov[i_end][j_end]==5) { S.push("LL"); i_end +=1; j_end -=2; } else if(mov[i_end][j_end]==6) { S.push("L"); i_end +=2; } } while(!S.empty()) { cout<> 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; }