Advertisement
StoneHaos

l_igor

Nov 9th, 2021
1,185
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <time.h>
  4. #include <stdlib.h>
  5. #include <stdio.h>
  6. #include <vector>
  7. #include <utility>
  8.  
  9. using namespace std;
  10.  
  11. typedef pair<int, int> pii;
  12.  
  13. int matrix[17][11] = {
  14.     {0, 5, 0, 11, 0, 12, 0, 9, 0, 5, 0},
  15.     {11, 0, 3, 0, 5, 0, 8, 0, 3, 0, 6},
  16.     {0, 7, 0, 5, 0, 10, 0, 8, 0, 7, 0},
  17.     {11, 0, 13, 0, 11, 0, 10, 0, 17, 0, 7},
  18.     {0, 11, 0, 5, 0, 4, 0, 12, 0, 13, 0},
  19.     {8, 0, 9, 0, 9, 0, 9, 0, 9, 0, 5},
  20.     {0, 6, 0, 11, 0, 10, 0, 5, 0, 8, 0},
  21.     {12, 0, 14, 0, 10, 0, 14, 0, 14, 0, 9},
  22.     {0, 10, 0, 5, 0, 9, 0, 7, 0, 9, 0},
  23.     {1, 0, 3, 0, 8, 0, 10, 0, 8, 0, 7},
  24.     {0, 5, 0, 6, 0, 4, 0, 6, 0, 14, 0},
  25.     {2, 0, 9, 0, 11, 0, 6, 0, 13, 0, 8},
  26.     {0, 7, 0, 4, 0, 8, 0, 9, 0, 6, 0},
  27.     {8, 0, 4, 0, 8, 0, 9, 0, 11, 0, 9},
  28.     {0, 8, 0, 11, 0, 13, 0, 5, 0, 10, 0},
  29.     {12, 0, 9, 0, 17, 0, 8, 0, 10, 0, 6},
  30.     {0, 8, 0, 16, 0, 2, 0, 5, 0, 7, 0},
  31. };
  32.  
  33. int main() {
  34.     for (int i = 0; i < 17; i += 2) {
  35.         for (int j = 0; j < 11; j += 2) {
  36.             if (i == 0 && j == 0) j += 2;
  37.             int mn = INT_MAX;
  38.             if (i - 2 >= 0) {
  39.                 mn = min(mn, matrix[i - 1][j] + matrix[i - 2][j]);
  40.             }
  41.             if (j - 2 >= 0) {
  42.                 mn = min(mn, matrix[i][j - 1] + matrix[i][j - 2]);
  43.             }
  44.             //printf("i = %d, j = %d, mn = %d\n", i, j, mn);
  45.             matrix[i][j] = mn;
  46.         }
  47.     }
  48.     vector<pii> v;
  49.     int i = 16;
  50.     int j = 10;
  51.     v.push_back(pii(i, j));
  52.     while (i != 0 || j != 0) {
  53.         if (i - 2 >= 0 && (matrix[i][j] == matrix[i - 1][j] + matrix[i - 2][j])) {
  54.             i -= 2;
  55.             v.push_back(pii(i, j));
  56.         }
  57.         else if (j - 2 >= 0 && (matrix[i][j] == matrix[i][j - 1] + matrix[i][j - 2])) {
  58.             j -= 2;
  59.             v.push_back(pii(i, j));
  60.         }
  61.     }
  62.     reverse(v.begin(), v.end());
  63.     for (auto p : v) {
  64.         cout << p.first << " " << p.second << endl;
  65.     }
  66.     cout << matrix[16][10] << endl;
  67.     return 0;
  68. }
  69.  
Advertisement
RAW Paste Data Copied
Advertisement