Количество туров через сетку m x n?

Question

Пусть Т (х, у) количество туров по 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

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

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

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

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

Answer 2

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

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

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

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) 

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

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