Advertisement
Guest User

Untitled

a guest
Dec 11th, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.97 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. template <typename T>
  4. void DeleteMatrix(T** matrix, int line) {
  5.   for (int i = 0; i < line; ++i) {
  6.     delete[] matrix[i];
  7.   }
  8.   delete[] matrix;
  9. }
  10.  
  11. int NumberOfDifferentWays(int n, int m) {
  12.   int** partial_solution = new int* [n];
  13.   for (int i = 0; i < n; ++i) {
  14.     partial_solution[i] = new int[m];
  15.   }
  16.  
  17.   for (int i = 0; i < n; ++i) {
  18.     for (int j = 0; j < m; ++j) {
  19.       partial_solution[i][j] = 0;
  20.     }
  21.   }
  22.   partial_solution[0][0] = 1;
  23.  
  24.   for (int k = 1; k < m; ++k) {
  25.     int j = k;
  26.     int i = 0;
  27.     while ((i >= 0) && (i < n) && (j >= 0) && (j < m)) {
  28.       partial_solution[i][j] =
  29.         (((i - 2 >= 0) && (j - 1 >= 0) && (i - 2 < n) && (j - 1 < m)) ? partial_solution[i - 2][j - 1] : 0) +
  30.           (((i - 2 >= 0) && (j + 1 >= 0) && (i - 2 < n) && (j + 1 < m)) ? partial_solution[i - 2][j + 1] : 0) +
  31.           (((i - 1 >= 0) && (j - 2 >= 0) && (i - 1 < n) && (j - 2 < m)) ? partial_solution[i - 1][j - 2] : 0) +
  32.           (((i + 1 >= 0) && (j - 2 >= 0) && (i + 1 < n) && (j - 2 < m)) ? partial_solution[i + 1][j - 2] : 0);
  33.  
  34.       ++i;
  35.       --j;
  36.     }
  37.   }
  38.  
  39.   for (int k = 1; k < n; ++k) {
  40.     int j = m - 1;
  41.     int i = k;
  42.     while ((i >= 0) && (i < n) && (j >= 0) && (j < m)) {
  43.       partial_solution[i][j] =
  44.         (((i - 2 >= 0) && (j - 1 >= 0) && (i - 2 < n) && (j - 1 < m)) ? partial_solution[i - 2][j - 1] : 0) +
  45.         (((i - 2 >= 0) && (j + 1 >= 0) && (i - 2 < n) && (j + 1 < m)) ? partial_solution[i - 2][j + 1] : 0) +
  46.         (((i - 1 >= 0) && (j - 2 >= 0) && (i - 1 < n) && (j - 2 < m)) ? partial_solution[i - 1][j - 2] : 0) +
  47.         (((i + 1 >= 0) && (j - 2 >= 0) && (i + 1 < n) && (j - 2 < m)) ? partial_solution[i + 1][j - 2] : 0);
  48.  
  49.       ++i;
  50.       --j;
  51.     }
  52.   }
  53.  
  54.   int result = partial_solution[n - 1][m - 1];
  55.   DeleteMatrix(partial_solution, n);
  56.  
  57.   return result;
  58. }
  59.  
  60. int main() {
  61.   int n = 0;
  62.   int m = 0;
  63.   std::cin >> n >> m;
  64.  
  65.   std::cout << NumberOfDifferentWays(n, m);
  66.  
  67.   return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement