#include #include #include #include #include #include #include typedef struct { int x, y; } vec2; float vec2_distance(const vec2 *a, const vec2 *b) { vec2 delta; delta.x = b->x - a->x; delta.y = b->y - a->y; return sqrtf((float)(delta.x * delta.x + delta.y * delta.y)); } int vec2_equal(const vec2 *a, const vec2 *b) { return a->x == b->x && a->y == b->y; } vec2 vec2_add(const vec2 *a, const vec2 *b) { vec2 v; v.x = a->x + b->x; v.y = a->y + b->y; return v; } vec2 vec2_sub(const vec2 *a, const vec2 *b) { vec2 v; v.x = a->x - b->x; v.y = a->y - b->y; return v; } 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. static int NUM_NEIGHBORS = 6; static vec2 neighbors[] = { { +0, -2 }, { +2, -1 }, { +2, +1 }, { +0, +2 }, { -2, +1 }, { -2, -1 } }; static const char *neighbor_names[] = { "L", "LL", "LR", "R", "UR", "UL" }; vec2 start = { i_start, j_start }; vec2 end = { i_end, j_end }; vec2 *closed_set = calloc(sizeof(vec2), n*n); int closed_set_count = 0; vec2 *open_set = calloc(sizeof(vec2), n*n); int open_set_count = 0; int *came_from = calloc(sizeof(int), n*n); for (int i = 0; i < n*n; ++i) { came_from[i] = -1; } float *g_score = calloc(sizeof(float), n*n); for (int i = 0; i < n*n; ++i) { g_score[i] = INFINITY; } g_score[start.x * n + start.y] = 0; float *f_score = calloc(sizeof(float), n*n); for (int i = 0; i < n*n; ++i) { f_score[i] = INFINITY; } open_set[open_set_count] = start; ++open_set_count; f_score[start.x * n + start.y] = vec2_distance(&start, &end); while (open_set_count) { vec2 current; float current_f; int current_i; for (int i = 0; i < open_set_count; ++i) { vec2 o = open_set[i]; float f = f_score[o.x * n + o.y]; if (!i || f <= current_f) { current = o; current_f = f; current_i = i; } } if (vec2_equal(¤t, &end)) { vec2 node; int num_nodes = 0; node = current; for (node = current; !vec2_equal(&start, &node);) { int move = came_from[node.x * n + node.y]; ++num_nodes; node = vec2_sub(&node, &neighbors[move]); } printf("%d\n", num_nodes); vec2 *path = calloc(num_nodes, sizeof(vec2)); node = current; int i; for (int i = 0; i < num_nodes; ++i) { int move = came_from[node.x * n + node.y]; path[i] = node; node = vec2_sub(&node, &neighbors[move]); } for (int i = 0; i < num_nodes; ++i) { node = path[num_nodes - i - 1]; int move = came_from[node.x * n + node.y]; const char *move_name = neighbor_names[move]; printf("%s ", move_name); } puts(""); free(path); goto cleanup; } memcpy(&open_set[current_i], &open_set[current_i + 1], sizeof(vec2) * (open_set_count - current_i)); --open_set_count; closed_set[closed_set_count] = current; ++closed_set_count; for (int i = 0; i < NUM_NEIGHBORS; ++i) { vec2 neighbor = vec2_add(¤t, &neighbors[i]); if (neighbor.x < 0 || neighbor.x >= n || neighbor.y < 0 || neighbor.y >= n) { continue; } int is_neighbor_in_closed_set = 0; for (int j = 0; j < closed_set_count; ++j) { vec2 c = closed_set[j]; if (vec2_equal(&neighbor, &c)) { is_neighbor_in_closed_set = 1; break; } } if (is_neighbor_in_closed_set) { continue; } int is_neighbor_in_open_set = 0; for (int j = 0; j < open_set_count; ++j) { vec2 o = open_set[j]; if (vec2_equal(&neighbor, &o)) { is_neighbor_in_open_set = 1; break; } } if (!is_neighbor_in_open_set) { open_set[open_set_count] = neighbor; ++open_set_count; } float tentative_score = g_score[current.x * n + current.y] + 1;// vec2_distance(¤t, &neighbor); int is_better_path = tentative_score < g_score[neighbor.x * n + neighbor.y]; if (!is_better_path) { continue; } came_from[neighbor.x * n + neighbor.y] = i; g_score[neighbor.x * n + neighbor.y] = tentative_score; f_score[neighbor.x * n + neighbor.y] = tentative_score + vec2_distance(&neighbor, &end); } } puts("Impossible"); cleanup: free(closed_set); free(open_set); free(came_from); free(g_score); free(f_score); } 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; }