Advertisement
StoneHaos

7

Jan 23rd, 2022
972
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <limits.h>
  4. #include <math.h>
  5.  
  6. typedef struct {
  7.     int x;
  8.     int y;
  9. } vec2;
  10. const int n = 17;
  11. const int m = 11;
  12. int matrix[n][m] = {
  13.     {0, 9, 0, 14, 0, 13, 0, 8, 0, 6, 0},
  14.     {8, 0, 3, 0, 5, 0, 8, 0, 3, 0, 7},
  15.     {0, 4, 0, 5, 0, 10, 0, 8, 0, 9, 0},
  16.     {6, 0, 12, 0, 11, 0, 11, 0, 11, 0, 7},
  17.     {0, 13, 0, 5, 0, 4, 0, 12, 0, 13, 0},
  18.     {5, 0, 6, 0, 5, 0, 9, 0, 7, 0, 5},
  19.     {0, 6, 0, 11, 0, 10, 0, 5, 0, 8, 0},
  20.     {10, 0, 14, 0, 13, 0, 15, 0, 14, 0, 9},
  21.     {0, 10, 0, 5, 0, 9, 0, 4, 0, 9, 0},
  22.     {7, 0, 12, 0, 7, 0, 12, 0, 8, 0, 7},
  23.     {0, 2, 0, 7, 0, 7, 0, 7, 0, 14, 0},
  24.     {8, 0, 8, 0, 15, 0, 6, 0, 11, 0, 8},
  25.     {0, 9, 0, 9, 0, 8, 0, 9, 0, 7, 0},
  26.     {9, 0, 11, 0, 7, 0, 8, 0, 14, 0, 2},
  27.     {0, 6, 0, 12, 0, 10, 0, 5, 0, 11, 0},
  28.     {14, 0, 9, 0, 10, 0, 9, 0, 10, 0, 5},
  29.     {0, 3, 0, 13, 0, 6, 0, 5, 0, 5, 0}
  30. };
  31.  
  32. int min(int a, int b) {
  33.     return ((a < b) ? a : b);
  34. }
  35.  
  36. int main(void) {
  37.     for (int i = 0; i < n; i += 2) {
  38.         for (int j = 0; j < m; j += 2) {
  39.             int mn = INT_MAX;
  40.             if (i > 0) {
  41.                 mn = min(mn, matrix[i - 2][j] + matrix[i - 1][j]);
  42.             }
  43.             if (j > 0) {
  44.                 mn = min(mn, matrix[i][j - 2] + matrix[i][j - 1]);
  45.             }
  46.             if (mn != INT_MAX)
  47.                 matrix[i][j] = mn;
  48.         }
  49.     }
  50.     vec2 way[(n + m) / 2];
  51.     int brd = 0;
  52.     int a = n - 1;
  53.     int b = m - 1;
  54.     while (a > 0 || b > 0) {
  55.         way[brd++] = {a, b};
  56.         int v = matrix[a][b];
  57.         if (a > 0 && v == (matrix[a - 2][b] + matrix[a - 1][b])) {
  58.             a -= 2;
  59.         }
  60.         else if (b != 0 && v == (matrix[a][b - 2] + matrix[a][b - 1])) {
  61.             b -= 2;
  62.         }
  63.     }
  64.     for (int i = 0; i < n; i ++) {
  65.         for (int j = 0; j < m; ++ j) {
  66.             printf("%2d ", matrix[i][j]);
  67.         }
  68.         printf("\n");
  69.     }
  70.     printf("\n");
  71.     printf("Min Way: %d\n", matrix[n - 1][m - 1]);
  72.     way[brd++] = {0, 0};
  73.     for (int i = brd - 1; i >= 0; -- i) {
  74.         printf("(%d, %d)", way[i].x, way[i].y);
  75.         if (i)
  76.             printf(" -> ");
  77.     }
  78.     printf("\n");
  79.     return 0;
  80. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement