Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- template <typename T>
- void DeleteMatrix(T** matrix, int line) {
- for (int i = 0; i < line; ++i) {
- delete[] matrix[i];
- }
- delete[] matrix;
- }
- int NumberOfDifferentWays(int n, int m) {
- int** partial_solution = new int* [n];
- for (int i = 0; i < n; ++i) {
- partial_solution[i] = new int[m];
- }
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < m; ++j) {
- partial_solution[i][j] = 0;
- }
- }
- partial_solution[0][0] = 1;
- for (int k = 1; k < m; ++k) {
- int j = k;
- int i = 0;
- while ((i >= 0) && (i < n) && (j >= 0) && (j < m)) {
- partial_solution[i][j] =
- (((i - 2 >= 0) && (j - 1 >= 0) && (i - 2 < n) && (j - 1 < m)) ? partial_solution[i - 2][j - 1] : 0) +
- (((i - 2 >= 0) && (j + 1 >= 0) && (i - 2 < n) && (j + 1 < m)) ? partial_solution[i - 2][j + 1] : 0) +
- (((i - 1 >= 0) && (j - 2 >= 0) && (i - 1 < n) && (j - 2 < m)) ? partial_solution[i - 1][j - 2] : 0) +
- (((i + 1 >= 0) && (j - 2 >= 0) && (i + 1 < n) && (j - 2 < m)) ? partial_solution[i + 1][j - 2] : 0);
- ++i;
- --j;
- }
- }
- for (int k = 1; k < n; ++k) {
- int j = m - 1;
- int i = k;
- while ((i >= 0) && (i < n) && (j >= 0) && (j < m)) {
- partial_solution[i][j] =
- (((i - 2 >= 0) && (j - 1 >= 0) && (i - 2 < n) && (j - 1 < m)) ? partial_solution[i - 2][j - 1] : 0) +
- (((i - 2 >= 0) && (j + 1 >= 0) && (i - 2 < n) && (j + 1 < m)) ? partial_solution[i - 2][j + 1] : 0) +
- (((i - 1 >= 0) && (j - 2 >= 0) && (i - 1 < n) && (j - 2 < m)) ? partial_solution[i - 1][j - 2] : 0) +
- (((i + 1 >= 0) && (j - 2 >= 0) && (i + 1 < n) && (j - 2 < m)) ? partial_solution[i + 1][j - 2] : 0);
- ++i;
- --j;
- }
- }
- int result = partial_solution[n - 1][m - 1];
- DeleteMatrix(partial_solution, n);
- return result;
- }
- int main() {
- int n = 0;
- int m = 0;
- std::cin >> n >> m;
- std::cout << NumberOfDifferentWays(n, m);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement