#include using namespace std; void print(vector > vec,int n){ for(int i=0;i= n || j< 0 || j>= n ) return true; return false; } void modify(vector > &vec,int is,int js,int n){ if( !isOutOfBoundary(is,js,n)){ if( !isOutOfBoundary(is,js+2,n) && vec[is][js+2]!=8) vec[is][js] = min(vec[is][js],1+vec[is][js+2]); if( !isOutOfBoundary(is,js-2,n) && vec[is][js-2]!=8) vec[is][js] = min(vec[is][js],1+vec[is][js-2]); if( !isOutOfBoundary(is+2,js+1,n) && vec[is+2][js+1]!=8) vec[is][js] = min(vec[is][js],1+vec[is+2][js+1]); if( !isOutOfBoundary(is+2,js-1,n) && vec[is+2][js-1]!=8) vec[is][js] = min(vec[is][js],1+vec[is+2][js-1]); if( !isOutOfBoundary(is-2,js+1,n) && vec[is-2][js+1]!=8) vec[is][js] = min(vec[is][js],1+vec[is-2][js+1]); if( !isOutOfBoundary(is-2,js-1,n) && vec[is-2][js-1]!=8) vec[is][js] = min(vec[is][js],1+vec[is-2][js-1]); } } void fillul(vector > &vec, int i_start, int j_start, int n){ for(int is = i_start;is >= 0;is--){ for(int js = j_start;js>=0;js--){ modify(vec,is,js,n); } } } void fillur(vector > &vec, int i_start, int j_start, int n){ for(int is = i_start;is < n;is++){ for(int js = j_start;js>=0;js--){ modify(vec,is,js,n); } } } void fillll(vector > &vec, int i_start, int j_start, int n){ for(int is = i_start;is >= 0;is--){ for(int js = j_start;js < n;js++){ modify(vec,is,js,n); } } } void filllr(vector > &vec, int i_start, int j_start, int n){ for(int is = i_start;is < n;is++ ){ for(int js = j_start;js > vec, int ie, int je, int n){ int val = vec[ie][je]; vector str; while( val > 0){ if( !isOutOfBoundary(ie,je+2,n) && vec[ie][je+2]== val-1){ je += 2; str.push_back("L"); } else if( !isOutOfBoundary(ie,je-2,n) && vec[ie][je-2]==val-1){ je -= 2; str.push_back("R"); } else if( !isOutOfBoundary(ie+2,je+1,n) && vec[ie+2][je+1]==val-1){ ie += 2; je += 1; str.push_back("UL"); } else if( !isOutOfBoundary(ie+2,je-1,n) && vec[ie+2][je-1]==val-1){ ie += 2; je -= 1; str.push_back("UR"); } else if( !isOutOfBoundary(ie-2,je+1,n) && vec[ie-2][je+1] == val-1){ ie -= 2; je += 1; str.push_back("LL"); } else if( !isOutOfBoundary(ie-2,je-1,n) && vec[ie-2][je-1] == val-1){ ie -= 2; je -= 1; str.push_back("LR"); } val--; } for(int i= str.size()-1;i >= 0;i--) cout << str[i]<<" "; cout < > vec(n,vector(n,n+1)); vec[i_start][j_start] = 0; fillul(vec,i_start,j_start,n); fillur(vec,i_start,j_start,n); fillll(vec,i_start,j_start,n); filllr(vec,i_start,j_start,n); //print(vec,n); if(vec[i_end][j_end] == n+1) cout<< "Impossible"<> 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; }