SHARE
TWEET

Untitled

a guest May 23rd, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "ReadWriter.h"
  2. //string, iostream included in "ReadWriter.h"
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7.  
  8. //Можно добавлять любые вспомогательные методы и классы для решения задачи.
  9.  
  10.  
  11. void calculateInCell(int N, int M, vector<vector<long long>> &field, int i, int j) {
  12.  
  13.     if (i == 0 && j == 0)
  14.         return;
  15.  
  16.     long long value = 0;
  17.     // первый
  18.     if (i - 2 >= 0 && j - 1 >= 0) {
  19.         if (field[i - 2][j - 1] == -1) {
  20.             calculateInCell(N, M, field, i - 2, j - 1);
  21.         }
  22.         value += field[i - 2][j - 1];
  23.     }
  24.     // второй
  25.     if (i - 2 >= 0 && j + 1 < M) {
  26.         if (field[i - 2][j + 1] == -1) {
  27.             calculateInCell(N, M, field, i - 2, j + 1);
  28.         }
  29.         value += field[i - 2][j + 1];
  30.     }
  31.     // третий
  32.     if (i - 1 >= 0 && j - 2 >= 0) {
  33.         if (field[i - 1][j - 2] == -1) {
  34.             calculateInCell(N, M, field, i - 1, j - 2);
  35.         }
  36.         value += field[i - 1][j - 2];
  37.     }
  38.     // четвертый
  39.     if (i + 1 < N && j - 2 >= 0) {
  40.         if (field[i + 1][j - 2] == -1) {
  41.             calculateInCell(N, M, field, i + 1, j - 2);
  42.         }
  43.         value += field[i + 1][j - 2];
  44.     }
  45.     field[i][j] = value;
  46. }
  47.  
  48. //Задача реализовать этот метод
  49. //param N - количество строк (rows) доски
  50. //param M - количество столбцов (columns) доски
  51. //return - количество способов попасть в правый нижний угол доски (клетка N-1, M-1, если считать что первая клетка 0,0)
  52. long long solve(int N, int M) {
  53.     vector<vector<long long>> field;
  54.     for (int i = 0; i < N; i++) {
  55.         field.push_back(vector<long long>());
  56.         for (int j = 0; j < M; j++)
  57.             field[i].push_back(-1);
  58.     }
  59.     field[0][0] = 1;
  60.     calculateInCell(N, M, field, N - 1, M - 1);
  61.     return field[N - 1][M - 1];
  62. }
  63.  
  64. int main(int argc, const char *argv[]) {
  65.     ReadWriter rw;
  66.  
  67.     int N = rw.readInt(); //количество строк (rows)
  68.     int M = rw.readInt(); //количество столбцов (columns)
  69.     //решение
  70.     long long res = solve(N, M);
  71.     //результат в файл
  72.     rw.writeLongLong(res);
  73.  
  74.     return 0;
  75. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top