#include #include #include #include #include #include #include int isPossible(int n, int i_start, int j_start, int i_end, int j_end) { int res = 1; /*check the rows*/ int distanceRow = i_start - i_end; if(distanceRow < 0){distanceRow = distanceRow * (-1);} if((distanceRow%2)!= 0){res = 0;} /*check the colums*/ int distanceColumn = j_start - j_end; if(distanceColumn < 0){distanceColumn = distanceColumn * (-1);} if((0 == distanceColumn) && (0 != distanceRow%4)) {res = 0;} else if((distanceColumn < distanceRow/2) && (0 != ((distanceRow/2)-distanceColumn)%2)){res = 0;} else if ((distanceColumn > distanceRow/2) && (0 != (distanceColumn - distanceRow/2)%2)) {res = 0;} return res; } void printMoves(int numberMoves, int* res) { int i; for(i = 0; i < numberMoves; i++) { switch(res[i]){ case 1: printf("UL "); break; case 2: printf("UR "); break; case 3: printf("R "); break; case 4: printf("LR "); break; case 5: printf("LL "); break; case 6: printf("L "); 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. if(0 == isPossible(n, i_start, j_start, i_end, j_end)){ printf("Impossible"); } else { int res[300]; int numberMoves = 0; int currentPosI = i_start; int currentPosJ = j_start; while((0 < (currentPosI-i_end)) && (0 <=(currentPosJ-j_end))){ res[numberMoves] = 1; numberMoves++; currentPosI -= 2; currentPosJ -= 1; } while((0 < (currentPosI-i_end)) && (0 >(currentPosJ-j_end))){ res[numberMoves] = 2; numberMoves++; currentPosI -= 2; currentPosJ += 1; } while((j_end-currentPosJ) > (i_end-currentPosI)/2){ res[numberMoves] = 3; numberMoves++; currentPosJ += 2; } while((0 > (currentPosI-i_end)) && (0 >=(currentPosJ-j_end))){ res[numberMoves] = 4; numberMoves++; currentPosI += 2; currentPosJ += 1; } while((0 > (currentPosI-i_end)) && (0 <(currentPosJ-j_end))){ res[numberMoves] = 5; numberMoves++; currentPosI += 2; currentPosJ -= 1; } while((0 == (currentPosI-i_end)) && (0 < (currentPosJ-j_end))){ res[numberMoves] = 6; numberMoves++; currentPosJ -= 2; } printf("%d\n", numberMoves); printMoves(numberMoves, res); } } int main() { int n; scanf("%i", &n); int i_start; int j_start; int i_end; int j_end; scanf("%i %i %i %i", &i_start, &j_start, &i_end, &j_end); printShortestPath(n, i_start, j_start, i_end, j_end); return 0; }