#include using namespace std; class Sample { public: int small, direction; }; bool visited[201][201]; Sample dp[201][201]; int dir[6][2] = { {-2, -1}, {-2, 1}, {0, 2}, {2, 1}, {2, -1}, {0, -2} }; Sample steps(int n, int i, int j, int i_end, int j_end) { if(i<0 || j<0 || i>=n || j>=n || (dp[i][j].small == INT_MAX && visited[i][j])) return {INT_MAX, INT_MAX}; if (i== i_end && j == j_end) return {0, INT_MAX}; if (dp[i][j].small < INT_MAX) return dp[i][j]; visited[i][j] = true; int small = INT_MAX, direction; for(int l=0;l<6;l++) { Sample step = steps(n, i+dir[l][0], j+dir[l][1], i_end, j_end); if(step.small < small) { small = step.small; direction = l; } } if (small == INT_MAX) return {INT_MAX, INT_MAX}; return dp[i][j] = {small+1, direction}; } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { int i, j; for(i=0;i<201;i++) { for(j=0;j<201;j++) { dp[i][j] = {INT_MAX, INT_MAX}; } } Sample ans = steps(n, i_start, j_start, i_end, j_end); if (ans.small == INT_MAX) cout<<"Impossible\n"; else { string str[] = {"UL", "UR", "R", "LR", "LL", "L"}; 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; }