Здравствуйте.
Ищу метод решения проблемы поиска слов в таблице (на манер сканвордов).
В данный момент уже запрограммированы все структуры данных, осталось только написать метод самого решения.
Алгоритм, каким я его вижу:
У нас есть квадратная матрица с кодами букв, каждая клетка матрицы соответственно имеет свою координату.
1) Сгенерировать список возможных «в принципе» слов, по координатам (буквы рядом - значит их можно связать).
По сути, задача по построению всевозможных графов на этой таблице.
И я абсолютно не понимаю как найти все возможные перестановки.
Условия:
- Графов в таблице должно быть больше одного.
- Каждый граф должен иметь больше 2х листьев
- Графы односвязные, ориентированные. Обратное направление - новый случай.
2) Используя сгенерированый список, проверить каждый вариант расположения букв на соответствие словарю.
Прошу натолкнуть на алгоритм действия, или показать на примере готового решения \ общей задачи.
Код не покажу, тк задача сугубо теоретическая, пока что.
UPD: Таки скорее по дискретной математике вопрос, просто у нас это в курсе вероятностей шло х)
