#include using namespace std; pair a[200][200]; void prop(int n,int i,int j){ if(i - 2 >= 0 && j - 1 >= 0 && (a[i-2][j-1].first == -1 || a[i-2][j-1].first > (a[i][j].first + 1))){ a[i-2][j-1].first = a[i][j].first + 1; a[i-2][j-1].second = "UL"; prop(n,i-2,j-1); } if(i - 2 >= 0 && j + 1 < n && (a[i-2][j+1].first == -1 || a[i-2][j+1].first > (a[i][j].first + 1))){ a[i-2][j+1].first = a[i][j].first + 1; a[i-2][j+1].second = "UR"; prop(n,i-2,j+1); } if(j + 2 < n && (a[i][j+2].first == -1 || a[i][j+2].first > (a[i][j].first + 1))){ a[i][j+2].first = a[i][j].first + 1; a[i][j+2].second = "R"; prop(n,i,j+2); } if(i + 2 < n && j + 1 < n && (a[i+2][j+1].first == -1 || a[i+2][j+1].first > (a[i][j].first + 1))){ a[i+2][j+1].first = a[i][j].first + 1; a[i+2][j+1].second = "LR"; prop(n,i+2,j+1); } if(i + 2 < n && j - 1 >=0 && (a[i+2][j-1].first == -1 || a[i+2][j-1].first > (a[i][j].first + 1))){ a[i+2][j-1].first = a[i][j].first + 1; a[i+2][j-1].second = "LL"; prop(n,i+2,j-1); } if(j - 2 >=0 && (a[i][j-2].first == -1 || a[i][j-2].first > (a[i][j].first + 1))){ a[i][j-2].first = a[i][j].first + 1; a[i][j-2].second = "L"; prop(n,i,j-2); } } 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. for(int i = 0;i v; int ii = i_end; int jj = j_end; while(ii != i_start || jj != j_start){ v.push_back(a[ii][jj].second); if(a[ii][jj].second == "UL"){ ii+=2; jj+=1; } if(a[ii][jj].second == "UR"){ ii+=2; jj-=1; } if(a[ii][jj].second == "R"){ jj-=2; } if(a[ii][jj].second == "LR"){ ii-=2; jj-=1; } if(a[ii][jj].second == "LL"){ ii-=2; jj+=1; } if(a[ii][jj].second == "L"){ jj+=2; } } for(int i = v.size()-1;i>=0;i--){ 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; }