C/C++

Помогите решить задачу на С++ , не получается никак

https://acmp.ru/index.asp?main=task&id_task=187
Представьте себе пчелиные соты – поле из шестиугольных клеток со стороной N. В верхней левой клетке A находится пчелка. За один ход она может переползти на клетку вниз, на клетку вниз-вправо или на клетку вверх-вправо (вверх и влево пчелка не ползает).

Требуется написать программу, которая найдет количество способов, которыми пчелка может доползти из клетки A в противоположную клетку B.
Входные данные
Входной файл INPUT.TXT содержит единственное число N – размеры шестиугольного поля (2 ≤ N ≤ 12).

Выходные данные
Выходной файл OUTPUT.TXT должен содержать единственное целое число – количество способов.
ВВОД: ВЫВОД :
2 11
3 291
Помогите пожалуйста с кодом
Александр Александрович
Александр Александрович
77
Тут что-то такое. Соты это двумерная матрица, числа в клетках это количества путей к данной клетке из верхней левой клетки если ходить только вправо и вниз. Как видим они возрастают в соотвесствии с определенной прогрессией
a[i][j] = a[i - 1][j] + a[i][j - 1]
Такое встречается в задачах на динамическое программирование
МП
Максим Петров
5 840
Лучший ответ
Владимир Латынин Матрица, конечно, двумерная, базара нет, как говорили в 90-е.
Но есть одна тонкость. Она - не квадратная, а из шестиугольных сот. Из центральной соты достижимы шесть других сот, а не 4, как в матрице.
Владимир Латынин Всё. Решил эту сик факин террибл задачу. Данные всё-таки совпадают. И насколько ж неудобно на C++ писать, это ад какой-то.
Мороки тут - изрядно, конечно. Питон:
 # Соты в кубических координатах

# Сумма трёх координат всегда равна 0

# Центр: (0, 0, 0)

# Верхний левый угол: (1-n, n-1, 0)

# Нижний правый угол: (n-1, 1-n, 0)

# Координат больше n-1 не существует

from functools import partial

from itertools import repeat



with open('input.txt', 'r') as fi:

    n = int(next(fi))



compose = lambda f, g: lambda *a: f(g(*a))

sub = partial(compose(tuple, map), int.__sub__)

valid = lambda c: max(map(abs, c))
Владимир Латынин
Владимир Латынин
54 053
Владимир Латынин C++, часть 1/2:
 #include 

#include 

#include 

#include 



using namespace std;



#define R(x, y) routes[x+bias][y+bias]



int main() {

    int n;

    {

        ifstream fi("INPUT.TXT");

        fi >> n;

    }



    const int deltas[][3] = {

        { 0, -1, 1 },  // вниз

        { 1, -1, 0 },  // вниз-вправо

        { 1, 0, -1 }   // вверх-вправо

    };

    const int size = 2 * n - 1;

    const int bias = n - 1;

    const int m = n - 1;

    unsigned long long routes[size][size];

    memset(routes, 0, sizeof(routes));

    R(-m, m) = 1;
Владимир Латынин часть 2/2:
 // ...продолжение...

    for (int x = -m; x							
 #include  

#include  

#include  

 

using namespace std; 

 

int main() { 

    ifstream input("INPUT.TXT"); 

    ofstream output("OUTPUT.TXT"); 

 

    int n; 

    input >> n; 

 

    vector dp(n * 2 - 1, vector(n, 0)); 

    dp[0][0] = 1; 

 

    for (int i = 1; i < n * 2 - 1; i++) { 

        for (int j = 0; j < n; j++) { 

            if (i < n) { 

                if (j > 0) { 

                    dp[i][j] += dp[i - 1][j - 1]; 

                } 

                dp[i][j] += dp[i - 1][j]; 

                if (j < n - 1) { 

                    dp[i][j] += dp[i - 1][j + 1]; 

                } 

            } else { 

                if (j > 0) { 

                    dp[i][j] += dp[i - 1][j - 1]; 

                } 

                if (j < n - 1) { 

                    dp[i][j] += dp[i - 1][j + 1]; 

                } 

            } 

        } 

    } 

 

    output
Алексей Красношлык
Алексей Красношлык
25 860
Владимир Латынин Ты это хоть раз запускал? Результат вообще не тот выдаётся.

Но спс за то, что напомнил, что надо на C++...

Похожие вопросы