C ++ Простой, но неразрешимый? думаю, нет

Question

Пусть T (x, y) будет количеством туров по сетке X × Y, таким образом:

1. тур начинается в верхнем левом квадрате
2. тур состоит изходов вверх, вниз, влево или вправо на один квадрат
3. тур посещает каждый квадрат ровно один раз, а
4. тур заканчивается в нижнем левом квадрате.

Легко видеть, например, что T (2,2) = 1, T (3,3) = 2, T (4,3) = 0 и T (3,4) = 4. Записатьпрограмма для вычисления T (10,4).

Я работал над этим часами ... Мне нужна программа, которая принимает размеры сетки в качестве входных данных и возвращает количество возможных туров?

Я работал над этим часами ... Мне нужна программа, которая принимает размеры сетки в качестве входных данных и возвращает количество возможных туров?

Я написал этот код для решенияпроблема ... Я не могу понять, как проверить все направления.

#include <iostream>

int grid[3][3];
int c = 0;

int main(){    
    solve (0, 0, 9);
}

int solve (int posx, int posy, steps_left){
    if (grid[posx][posy] = 1){
        return 0;
    }
    if (steps_left = 1 && posx = 0 && posy = 2){
        c = c+1;
        return 0;
    }
    grid[posx][posy] = 1;
    // for all possible directions
    {
        solve (posx_next, posy_next, steps_left-1)
    }
    grid[posx][posy] = 0;
}

Алгоритм @KarolyHorvath Вам нужна некоторая структура данных, чтобы представить состояниеячейки в сетке (посещенные / не посещенные).

Ваш алгоритм:

step(posx, posy, steps_left)
    if it is not a valid position, or already visited
        return
    if it's the last step and you are at the target cell
        you've found a solution, increment counter
        return
    mark cell as visited             
    for each possible direction:
       step(posx_next, posy_next, steps_left-1)
    mark cell as not visited

и выполняется с шагом (0, 0, sizex * sizey)

Answer 1

Вы действительно должны выбрать отладчик и посмотреть, что происходит на маленькой доске (2x2, 3x3).

Одна очевидная проблема заключается в том, что = это назначение, а не сравнение.Сравните с ==.

Есть еще проблемы.Найди их.

Answer 2

Это не сложно, так как вам дали алгоритм.Чтобы решить эту проблему, вам, вероятно, понадобится какая-то динамическая структура данных (если вы не заинтересованы только в точном случае T (10,4)).В остальном, слева равен -1 по индексу x, справа +1, а вниз - -1 по измерению y, вверх +1.Добавьте проверку границ и подтверждение того, что вы не посещали, и работа сделана.

Но мне интересно, сколько времени займет такой очевидный алгоритм.Существует четыре варианта решения для каждой ячейки;для сорока ячеек Т (10,4) это 4 ^ 40 решений.Что неосуществимо.Такие вещи, как устранение уже посещенных ячеек и проверка границ, устраняют множество ветвей, но все же ... Цель конкурса может заключаться в том, чтобы найти лучший алгоритм.