#include #include #include using namespace std; // all 6 possible knight moves described as vectors [dx,dy] const int dx[6] = { -1, 1, 2, 1, -1, -2 }; const int dy[6] = { -2, -2, 0, 2, 2, 0 }; const int REV[6] = { 3, 4, 5, 0, 1, 2 }; const string ASSTRING[6] = { "UL", "UR", "R", "LR", "LL", "L" }; const int UNEXPLORED = 1000; typedef struct _pt2D { int x, y; } Pt2D; // Start and end points Pt2D ST; Pt2D EN; // Board int B[200][200]; int N; // size of the board // for backtracking int T[200][200]; //Breath first search void BFS() { queue q; q.push(ST); int stepcount = 0; B[ST.x][ST.y] = stepcount; bool found = false; while (!q.empty()) { Pt2D node = q.front(); q.pop(); int count = B[node.x][node.y]; for (int d = 0; d < 6; ++d) { int x = node.x + dx[d]; if (x < 0 || x >= N) continue; int y = node.y + dy[d]; if (y < 0 || y >= N) continue; if (B[x][y] == UNEXPLORED) { B[x][y] = count + 1; T[x][y] = REV[d]; if (x == EN.x && y == EN.y) { found = true; break; } Pt2D NewNode = { x, y }; q.push(NewNode); } } if (found == true) break; } } //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. //} void printShortestPath(int gridsize, int starty, int startx, int endy, int endx) { // initialize N = gridsize; ST.x = startx; ST.y = starty; EN.x = endx; EN.y = endy; for (int x = 0; x < 200; ++x) { for (int y = 0; y < 200; ++y) { B[x][y] = UNEXPLORED; } } B[startx][starty] = 0; // run breadth first search if (startx != endx || starty != endy) BFS(); // backtrack from end to recreate the path if (B[endx][endy] == UNEXPLORED) { fprintf(stdout, "Impossible\n"); } else { vector path; int stepcount = B[endx][endy]; fprintf(stdout, "%d\n", stepcount); int curx = endx; int cury = endy; for (int i = 0; i < stepcount; ++i) { int d = T[curx][cury]; path.push_back(REV[d]); curx += dx[d]; cury += dy[d]; } for (int i = 0; i < stepcount; ++i) { if (i > 0) fprintf(stdout, " "); fprintf(stdout, "%s", ASSTRING[path[stepcount - i - 1]].c_str()); } if (stepcount > 0) fprintf(stdout, "\n"); } } int main() { int n; cin >> 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; }