с помощью возврата, чтобы найти слово в матрице

Question

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

G O P
N N A
A B E

и правила таковы, что можно перемещаться по горизонтали, вертикали и диагонали из любой позиции, то нам нужно сказать, содержит ли вышеуказанная матрица слово «GONE».Здесь мы можем сначала сохранить положение всех G (если> 1 G присутствует) и начать проверку с каждого из этих положений, но как проверить с помощью обратного отслеживания?Спасибо.

Answer 1

Эта игра называется Boggle .Вот хорошая тема на SO об этом (включая пример кода).

Answer 2

Я буду псевдокодировать алгоритм

Найти начальную букву из вашей функции начала обратного хода слова с этой позицией (передать следующую букву или следующую позицию буквы)

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

HTH, не стесняйтесь спрашивать разъяснения, если вам нужно.