/* ** *** @üťhöř : Řëwä Mąťhúŕ @Śťaťüš : Sťïľľ Ïñ Çöñšťŕūçťīöñ @Ďäťë : 16 Jäñ 2018 ** *** */ //Below code is making reference through points and giving an reference by Const. // Pardon me i Will soon make some comments to illustrate all this code processing. #include #include #include #include /* and not not_eq */ #include /* add -lm to command line to compile with this header */ #include #define map_size_rows 10 #define map_size_cols 10 char map[map_size_rows][map_size_cols] = { {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 1, 1, 1, 0, 1}, {1, 0, 0, 1, 0, 0, 0, 1, 0, 1}, {1, 0, 0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 0, 1, 1, 1, 1, 1, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 1, 0, 1, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1} }; /* description of graph node */ struct stop { double col, row; /* array of indexes of routes from this stop to neighbours in array of all routes */ int * n; int n_len; double f, g, h; int from; }; int ind[map_size_rows][map_size_cols] = { {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1} }; /* description of route between two nodes */ struct route { /* route has only one direction! */ int x; /* index of stop in array of all stops of src of this route */ int y; /* intex of stop in array of all stops od dst of this route */ double d; }; //all variable are defined and use for tracing and mapping the path and finding the cost estimated. int main() { int i, j, k, l, b, found; int p_len = 0; int * path = NULL; int c_len = 0; int * closed = NULL; int o_len = 1; int * open = (int*)calloc(o_len, sizeof(int)); double min, tempg; int s; int e; int current; int s_len = 0; struct stop * stops = NULL; int r_len = 0; struct route * routes = NULL; for (i = 1; i < map_size_rows - 1; i++) { for (j = 1; j < map_size_cols - 1; j++) { if (!map[i][j]) { ++s_len; stops = (struct stop *)realloc(stops, s_len * sizeof(struct stop)); int t = s_len - 1; stops[t].col = j; stops[t].row = i; stops[t].from = -1; stops[t].g = DBL_MAX; stops[t].n_len = 0; stops[t].n = NULL; ind[i][j] = t; } } } /* index of start stop */ s = 0; /* index of finish stop */ e = s_len - 1; for (i = 0; i < s_len; i++) { stops[i].h = sqrt(pow(stops[e].row - stops[i].row, 2) + pow(stops[e].col - stops[i].col, 2)); } //mapping the routes tonfind the girfriend. for (i = 1; i < map_size_rows - 1; i++) { for (j = 1; j < map_size_cols - 1; j++) { if (ind[i][j] >= 0) { for (k = i - 1; k <= i + 1; k++) { for (l = j - 1; l <= j + 1; l++) { if ((k == i) and (l == j)) { continue; } if (ind[k][l] >= 0) { ++r_len; routes = (struct route *)realloc(routes, r_len * sizeof(struct route)); int t = r_len - 1; routes[t].x = ind[i][j]; routes[t].y = ind[k][l]; routes[t].d = sqrt(pow(stops[routes[t].y].row - stops[routes[t].x].row, 2) + pow(stops[routes[t].y].col - stops[routes[t].x].col, 2)); ++stops[routes[t].x].n_len; stops[routes[t].x].n = (int*)realloc(stops[routes[t].x].n, stops[routes[t].x].n_len * sizeof(int)); stops[routes[t].x].n[stops[routes[t].x].n_len - 1] = t; } } } } } } open[0] = s; stops[s].g = 0; stops[s].f = stops[s].g + stops[s].h; found = 0; while (o_len and not found) { min = DBL_MAX; for (i = 0; i < o_len; i++) { if (stops[open[i]].f < min) { current = open[i]; min = stops[open[i]].f; } } if (current == e) { found = 1; ++p_len; path = (int*)realloc(path, p_len * sizeof(int)); path[p_len - 1] = current; while (stops[current].from >= 0) { current = stops[current].from; ++p_len; path = (int*)realloc(path, p_len * sizeof(int)); path[p_len - 1] = current; } } //this code block is used for matching and perform mapping with path. for (i = 0; i < o_len; i++) { if (open[i] == current) { if (i not_eq (o_len - 1)) { for (j = i; j < (o_len - 1); j++) { open[j] = open[j + 1]; } } --o_len; open = (int*)realloc(open, o_len * sizeof(int)); break; } } ++c_len; closed = (int*)realloc(closed, c_len * sizeof(int)); closed[c_len - 1] = current; for (i = 0; i < stops[current].n_len; i++) { b = 0; for (j = 0; j < c_len; j++) { if (routes[stops[current].n[i]].y == closed[j]) { b = 1; } } if (b) { continue; } tempg = stops[current].g + routes[stops[current].n[i]].d; b = 1; //checking the length of the path for searching the estimated cost on that forest. if (o_len > 0) { for (j = 0; j < o_len; j++) { if (routes[stops[current].n[i]].y == open[j]) { b = 0; } } } // for mapping with each path of the forest. if (b or (tempg < stops[routes[stops[current].n[i]].y].g)) { stops[routes[stops[current].n[i]].y].from = current; stops[routes[stops[current].n[i]].y].g = tempg; stops[routes[stops[current].n[i]].y].f = stops[routes[stops[current].n[i]].y].g + stops[routes[stops[current].n[i]].y].h; //realloc works here for locating and reusing memory blocks. if (b) { ++o_len; open = (int*)realloc(open, o_len * sizeof(int)); open[o_len - 1] = routes[stops[current].n[i]].y; } } } } /*/mapping the graph and the path of yours to go towards the forest path to find the girlfriend. this block of code is used to trace your choosen path.*/ for (i = 0; i < map_size_rows; i++) { for (j = 0; j < map_size_cols; j++) { if (map[i][j]) { putchar(0xdb); } else { b = 0; for (k = 0; k < p_len; k++) { if (ind[i][j] == path[k]) { ++b; } } if (b) { putchar('x'); } else { putchar('.'); } } } putchar('\n'); } /*/ if the girlfriend not found at the edge of forest then it willagain backtrack the path to find her.*/ if (not found) { puts("I AM POSSIBLE"); } else { printf("path cost is %d:\n", p_len); for (i = p_len - 1; i >= 0; i--) { printf("(%1.0f, %1.0f)\n", stops[path[i]].col, stops[path[i]].row); } } /*/ the below code is used for making free the memory blocks of different used varable like stops, routes, path, open, closed which is used for following an path and finding out the girlfriend in the forest.*/ for (i = 0; i < s_len; ++i) { free(stops[i].n); } free(stops); free(routes); free(path); free(open); free(closed); return 0; }

Man In search of Girl friend:-) Part II