Advertisement
Guest User

Untitled

a guest
May 23rd, 2019
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.35 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement