Количество туров по сетке mxn?

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).

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

Answer 1

Поскольку вы новичок в отслеживании, это может дать вам представление о том, как вы можете решить эту проблему:

Вам нужна некоторая структура данных для представления состояния ячеек в сетке (посещено / не посещено).

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

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

и запустить с

step(0, 0, sizex*sizey)

Основными строительными блоками отслеживания являются: оценка текущего состояния, маркировка, рекурсивный шаг и снятие отметки.

Это отлично подойдет для небольших досок. Настоящее веселье начинается с больших досок, где вы должны обрезать ветви на дереве, которые не разрешимы (например: есть недостижимая область не посещаемых ячеек).

Answer 2

Назначенное упражнение хорошее.Это заставляет вас продумывать несколько концепций, шаг за шагом.Я не могу продумать все концепции для вас, но, возможно, я могу помочь, задав следующий вопрос:

В какой-то момент ваша программа должна представлять собой частично завершенный тур. То естьдолжен представлять путь, который еще не прошел через все квадраты и еще не достиг своей цели в левом нижнем углу, но который мог бы сделать оба, если путь был позже расширен.Как вы хотите представить частично завершенный тур?

Если вы можете ответить на вопрос и понять концепцию рекурсии, то есть подозрение, что вы можете решить проблему с некоторымиработать, но без особых проблем.Представлять частично завершенный тур - это ваше препятствие, поэтому я рекомендую вам поработать над этим.

Обновление: См. Комментарий @KarolyHorvath ниже.Если вы еще не научились использовать динамически выделяемую память (или, что то же самое, контейнеры STL, такие как std :: vector и std :: list), тогда вам лучше следовать его подсказке, которая в любом случае является хорошим советом.