#include #include #include #include #include #include #include typedef struct stepRec{ int prev; int dir; }stepRec; int pointToIndex(int n, int i, int j){ return (i*n+j); } int* getNeighbors(int n, int ind){ int *A = malloc(sizeof(int) * 6); for (int i=0; i<6; i++) A[i] = -1; int i = ind / n; int j = ind - (i * n); if (i > 1) { if (j > 0) A[0] = (i-2)*n + (j-1); // UpperLeft if (j+1 < n) A[1] = (i-2)*n + (j+1); // UpperRight } if (j+2 < n) A[2] = i*n + (j+2); //Right if (i+2 < n) { if (j+1 < n) A[3] = (i+2)*n + (j+1); // LowerRight if (j > 0) A[4] = (i+2)*n + (j-1); // LowerLeft } if (j-2 >= 0) A[5] = i*n + (j-2); // Left return A; } 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 ((i_start-i_end) % 2 != 0) { printf("Impossible\n"); return; } int nn = n * n; int *moves = malloc(sizeof(int) * nn); int *queue = malloc(sizeof(int) * nn); stepRec *steps = malloc(sizeof(stepRec) * nn); for (int i=0; i= 0) { if (moves[neighbors[i]] == -1) { moves[neighbors[i]] = moves[queue[q_pop]] + 1; steps[neighbors[i]].prev = queue[q_pop]; steps[neighbors[i]].dir = i; if (neighbors[i] == end_ind) { printf("%d\n", moves[neighbors[i]]); int k = end_ind; static char *dirs[] = {"UL ", "UR ", "R ", "LR ", "LL ", "L "}; int *path = malloc(sizeof(int)*moves[neighbors[i]]); for (int j=moves[neighbors[i]]-1; j>=0; j--){ path[j] = steps[k].dir; k = steps[k].prev; } for (int j=0; j