Задать вопрос

Сколько вариантов путей есть для поля 4х4, если ходить можно вправо, вниз, вправо-вниз?

Считается ли это по формуле и куда рыть?

А если полей 5?6?7?
upd исправил пару опечаток
  • Вопрос задан
  • 4336 просмотров
Подписаться 3 Оценить 9 комментариев
Пригласить эксперта
Ответы на вопрос 4
@oandrew
Сам сталкивался с похожей задачей, если я вас правильно понял.
habrahabr.ru/qa/6563/

А вот ссылка где подробно все рассказывается
mathworld.wolfram.com/Self-AvoidingWalk.html

В итоге общей формулы нет(
Но это если ваша задача совпадает с тем, как я вас понял.
Ответ написан
Комментировать
@Disasm
Попробуйте решить задачу с помощью динамического программирования. Может быть даже в общем виде получится.
Ответ написан
Комментировать
@oandrew

#include <iostream>
#include <cstdlib>
using namespace std;

#define ROWS 4
#define COLS 4

int f(int row, int col) {
    if(row == 0 && col == 0)
        return 1;
    int result = 0;
    if(row > 0)
        result += f(row - 1, col);
    if(row > 0 && col > 0)
        result += f(row - 1, col - 1);
    if(col > 0)
        result += f(row, col - 1);
    return result;
}
int main() {
    cout << f(ROWS - 1,COLS - 1);
    system("pause"); 
}


Вот решение задачи.
При 4х4 будет 63
Ответ написан
kulinich
@kulinich
С++ программист
Для уточнения условия:
image
Мне кажется автор это имеет ввиду.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

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