#include #include #include using namespace std; int x[] = {-1,1,2,1,-1,-2}; int y[] = {-2,-2,0,2,2,0}; class Node { public: int x,y,d; Node(int x,int y,int d) { this->x = x; this->y = y; this->d = d; } Node(){} }; void printShortestPath(int n,int si,int sj,int ei,int ej) { queue< Node > que; bool visited[n][n]; memset(visited,false,sizeof(visited)); string check[n][n]; check[si][sj] = "S"; que.push(Node(sj,si,0)); visited[si][sj] = true; int res = -1; while(!que.empty()) { Node cur = que.front(); que.pop(); int cx = cur.x,cy = cur.y,cd = cur.d; if(cx == ej && cy == ei) { res = cd; break; } for(int i=0;i<6;i++) { if(cx+x[i] < 0 || cx+x[i] >= n || cy+y[i] < 0 || cy+y[i] >= n) continue; else if(visited[cy+y[i]][cx+x[i]]) continue; if(i == 0) check[cy+y[i]][cx+x[i]] = "UL"; else if(i == 1) check[cy+y[i]][cx+x[i]] = "UR"; else if(i == 2) check[cy+y[i]][cx+x[i]] = "R"; else if(i == 3) check[cy+y[i]][cx+x[i]] = "LR"; else if(i == 4) check[cy+y[i]][cx+x[i]] = "LL"; else check[cy+y[i]][cx+x[i]] = "L"; visited[cy+y[i]][cx+x[i]] = true; que.push(Node(cx+x[i],cy+y[i],cd+1)); } } if(res == -1) { cout<<"Impossible"< r; int ci = ei,cj = ej; while(true) { r.push_back(check[ci][cj]); if(check[ci][cj] == "UL") cj += 1, ci += 2; else if(check[ci][cj] == "UR") cj -= 1, ci += 2; else if(check[ci][cj] == "R") cj -= 2; else if(check[ci][cj] == "LR") cj -= 1, ci -= 2; else if(check[ci][cj] == "LL") cj += 1, ci -= 2; else if(check[ci][cj] == "L") cj += 2; else if(check[ci][cj] == "S") break; } for(int i=r.size()-2;i>=0;i--) cout<>n>>si>>sj>>ei>>ej; printShortestPath(n,si,sj,ei,ej); }