Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "ReadWriter.h"
- //string, iostream included in "ReadWriter.h"
- #include <vector>
- using namespace std;
- //Можно добавлять любые вспомогательные методы и классы для решения задачи.
- void calculateInCell(int N, int M, vector<vector<long long>> &field, int i, int j) {
- if (i == 0 && j == 0)
- return;
- long long value = 0;
- // первый
- if (i - 2 >= 0 && j - 1 >= 0) {
- if (field[i - 2][j - 1] == -1) {
- calculateInCell(N, M, field, i - 2, j - 1);
- }
- value += field[i - 2][j - 1];
- }
- // второй
- if (i - 2 >= 0 && j + 1 < M) {
- if (field[i - 2][j + 1] == -1) {
- calculateInCell(N, M, field, i - 2, j + 1);
- }
- value += field[i - 2][j + 1];
- }
- // третий
- if (i - 1 >= 0 && j - 2 >= 0) {
- if (field[i - 1][j - 2] == -1) {
- calculateInCell(N, M, field, i - 1, j - 2);
- }
- value += field[i - 1][j - 2];
- }
- // четвертый
- if (i + 1 < N && j - 2 >= 0) {
- if (field[i + 1][j - 2] == -1) {
- calculateInCell(N, M, field, i + 1, j - 2);
- }
- value += field[i + 1][j - 2];
- }
- field[i][j] = value;
- }
- //Задача реализовать этот метод
- //param N - количество строк (rows) доски
- //param M - количество столбцов (columns) доски
- //return - количество способов попасть в правый нижний угол доски (клетка N-1, M-1, если считать что первая клетка 0,0)
- long long solve(int N, int M) {
- vector<vector<long long>> field;
- for (int i = 0; i < N; i++) {
- field.push_back(vector<long long>());
- for (int j = 0; j < M; j++)
- field[i].push_back(-1);
- }
- field[0][0] = 1;
- calculateInCell(N, M, field, N - 1, M - 1);
- return field[N - 1][M - 1];
- }
- int main(int argc, const char *argv[]) {
- ReadWriter rw;
- int N = rw.readInt(); //количество строк (rows)
- int M = rw.readInt(); //количество столбцов (columns)
- //решение
- long long res = solve(N, M);
- //результат в файл
- rw.writeLongLong(res);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement