Лабиринт: вычислить количество маршрутов нечетной длины - C (СИ)

Формулировка задачи:

Коридорам лабиринта разрешается двигаться только в направлениях, указанных стрелками. Человек вошел в комнату A и, выбирая случайным образом коридоры, пытается выйти через комнату D. Определите все возможные маршруты, при которых не более чем за семь переходов человек достигнет цели. Вычислите количество соответствующих маршрутов длиной три перехода; пять; семь; (2 * n + 1) переходов.

Решение задачи: «Лабиринт: вычислить количество маршрутов нечетной длины»

Листинг программы

const int N=7;
int r[N+1];
 
void f(char c, int l, string s) {
    if (l>N) return;
    if (c=='d') r[l]++;
    
    cout<<s<<"-  "<<c<<'\n';
    switch (c) {  
        case 'a':  
            f('b', l+1, s+"    ");  
            break;  
        case 'b':  
            f('c', l+1, s+"   |");  
            f('c', l+1, s+"   |");  
            f('a', l+1, s+"    ");  
            break;  
        case 'c':  
            f('b', l+1, s+"   |");  
            f('d', l+1, s+"    ");  
            break;
        }
}
 
int main() {
    f('a', 0, "");
    for (int i=0; i<=N; i++) if (r[i]) cout<<i<<" steps: "<<r[i]<<" ways\n";
}

Объяснение кода листинга программы

В этом коде представлена реализация функции для поиска количества маршрутов в лабиринте.

В первой строке объявляется константа N, которая определяет количество клеток в лабиринте.
Затем объявляется массив r, который будет использоваться для хранения количества маршрутов для каждой клетки.
Функция f принимает три аргумента: символ текущей клетки, номер текущей клетки и строку, представляющую текущий маршрут.
Если номер текущей клетки больше N, функция завершается.
Если символ текущей клетки равен 'd', то в массиве r увеличивается значение для текущей клетки.
Выводится текущий маршрут, символ текущей клетки и номер текущей клетки.
Используется оператор switch для определения следующего шага в зависимости от символа текущей клетки.
В случае 'a' вызывается функция f с символом 'b', номером текущей клетки плюс один и текущий маршрут с добавлением дополнительного текста.
В случае 'b' вызывается функция f с символом 'c', номером текущей клетки плюс один и текущий маршрут с добавлением дополнительного текста.
В случае 'c' вызывается функция f с символом 'b', номером текущей клетки плюс один и текущий маршрут с добавлением дополнительного текста.
В основной функции main вызывается функция f с символом 'a', нулевым номером и пустой строкой.
Затем выполняется цикл, который проходит по всем номерам от 0 до N и выводит количество маршрутов для каждого номера. Обратите внимание, что этот код реализует простую модель лабиринта и не учитывает такие вещи, как направление движения или блокировки.