/* Have you ever had to look at * the task of finding the best route? * That is, how to get from point A to * point B in the shortest possible time? * * Then this code is for you! * * Let's model this task. * * Consequently, let's get a map of the * area in the form of a matrix * of size 'row' x 'col'. * Each cell of which is a specific segment * in the path. * It takes some time to go through this * section. This 'time' - we note in the * form of the values of the elements of * our matrix. * * 🅰_ _ _ _ _ * |6|5|2|1|9| * - - - - - * |8|7|1|3|3| * - - - - - * |5|9|1|1|7| * - - - - - * |7|7|8|7|8| * - - - - - * |7|6|2|7|1| * - - - - - 🅱 * * Point A is the upper left corner of the * matrix[0][0], point B is the lower * right corner of the * matrix[row -1][col - 1]. * The path that you need to go is * a curved line. * On it you can move only to the right ➡ * or down ⬇ from the top cell. * * A sample of possible paths: * ___ _____ | * | | | * |_ | | * | | | * |_ | |_____ * * So, here is the task to go through such * matrix cells, where the total sum of * the values of these cells will be * the smallest among all possible options. * * For our example, the next line will be * the desired path. For which the total * time spent is 31. * * 🅰 * 6 5 2 * 1 * 1 1 * 7 * 7 1 * 🅱 *********************************** * 🏁 For the program it is necessary * to enter data. Namely, the size of our * matrix (map area) 'row' and 'col'. * 🔖 Enter two integers, separated by * a space. * For example: 7 8 **********************************/ #include #include #include /* I will need to choose the least * of two values. */ #define MIN(a, b) ((a < b) ? a : b) /* Functions: * to generate a matrix 'row' x 'col' * with random values */ void get_road_map(int**, int, int); /* to display the matrix (map) on the * screen.*/ void show_road_map(int*, int, int); /* to find the optimal path. */ void find_best_route(int*, int, int); /* Since in this code I allocate memory * dynamically, I will need to clear it. */ void _free(int**); /********** 🔴 Main implementation 🔴 ***/ int main() { int* p = NULL; int row = 5, col = 5; scanf("%i %i", &row, &col); get_road_map(&p, row, col); show_road_map(p, row, col); find_best_route(p, row, col); _free(&p); return 0; } /*******************🇪🇳🇩************/ /*****🔺 Description of functions 🔺 ***** * The first two I will not describe in * detail, and so everything is clear. */ void get_road_map(int** p, int row, int col) { *p = (int*)malloc(sizeof(int) * row * col); if (!*p) return; srand(time(NULL)); for (int i = 0; i < row; i++) for (int j = 0; j < col; j++) *(*p + (i * col) + j) = rand() % 9 + 1; } void show_road_map(int* p, int row, int col) { if (!p) return; printf("The road map:\n\n"); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) printf("%i ", *(p + (i * col) + j)); printf("\n"); } } /* The most interesting thing here! ℹ*/ void find_best_route(int* p, int row, int col) { /* I allocate memory for the temporary * matrix, which will be the same size * as the main */ int* tmp = (int*)malloc(sizeof(int) * row * col); if (!tmp || !p) return; /* The algorithm is based on dynamic * programming. That is, the division * of a large task into solving small * subtasks (a simple definition; for * specifics, refer to Wikipedia😉) * * So, in order to follow the dynamic * programming, I will record the * result (the sum of the values of the * cells) in each cell of the temporary * table. The result should be * understood as the sum of the value * of this cell and the result for the * previous cell from which the * movement has been made. * * Is not it clear?😏 I think the * following will help you. * * Little steps (read - subtasks) to * solve our main task. * * ◽1 subtask: matrix 1 x 1 * 6 => 6 * * ◽2 subtask: matrix 2 x 2 * 6 5 6 11 * 8 7 => 14 (21 or 18) * * 6 + 5 = 11 * 6 + 8 = 14 * and 11 + 7 = 18 or 14 + 7 = 21 ? * * Note. Under the terms of the task it * is necessary to find the shortest * path (the one on which we will spend * the least time). * So for our sub task, in such an * optimal way is the following: * 6 ➡ 5 ➡ 7, * because for passing through it we * will spend only 🔔18 units of time. * And our tmp matrix will look like * this: * 6 11 * 14 18 * * ◽3 subtask: matrix 3 x 3 * 6 11 2 6 11 13 * 14 18 1 => 14 18 (19 or 14) * 5 9 1 19 (28 or 27) ??? * * (! we choose the minimum !) * * 6 11 13 6 11 13 * => 14 18 14 => 14 18 14 * 19 27 (15 or 28) 19 27 15 * * So an optimal way is * 6 ➡ 5 ➡ 2 ➡ 1 ➡ 1 and * total = 15 * * 6 5 2 * * * 1 * * * 1 * * And so on ... * And here is an example of how all of * this, given above, is implemented in * the code ⬇*/ for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (i == 0 && j == 0) *tmp = *p; else if (i == 0) *(tmp + j) = *(p + j) + *(tmp + (j - 1)); else if (j == 0) *(tmp + (i * col)) = *(p + (i * col)) + *(tmp + ((i - 1) * col)); else *(tmp + (i * col) + j) = *(p + (i * col) + j) + MIN(*(tmp + ((i - 1) * col) + j), *(tmp + (i * col) + (j - 1))); } } printf("\nThe least amount of time:\n\n%i\n", *(tmp + (row * col - 1))); /* In this algorithm, I go through all * the cells of the temporary result * matrix and write the value '-1' into * those cells that are part of the * optimal path. I start the iteration * from point B..... */ *(tmp + (row * col - 1)) = -1; for (int i = row - 1, j = col - 1, c = row + col - 2; c > 0; c--) { if (i == 0 && j == 0) break; else if (i == 0) j--; else if (j == 0) i--; else *(tmp + (i * col) + (j - 1)) < *(tmp + ((i - 1) * col) + j) ? j-- : i--; *(tmp + (i * col) + j) = -1; } /* '-1' is a kind of label that I need * to display the optimal path to the * screen ... */ printf("\nThe best route:\n\n"); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (*(tmp + (i * col) + j) == -1) printf("%i ", *(p + (i * col) + j)); else printf("%c ", '.'); } printf("\n"); } if (tmp) free(tmp); } void _free(int** p) { if (!*p) return; free(*p); *p = NULL; }

Search for the optimal path