Составление цепочки слов

Доброго времени суток!
Помогите построить цепочку слов минимальной длины (похоже на транспортную задачу)
Например, нужно из нескольких слов, (допустим, волг, полг, голг, ролг) составить цепочку от слова "долг" к слову "полк". Получится это следующим образом: Долг - волг - полг - полк. Слова одинаковой длины и могут отличаться только одной буквой.

Добавлено через 23 часа 7 минут
Проблема решена. Додумался.
Алгоритм "в двух словах":
Пусть имеется вектор слов.
Изначально пройтись по нему на наличие легкого поиска (по одному элементу). Например Долг - Долк - Полк
Если таких вариантов не нашлось, организовать цикл со вложенным циклом. Первый цикл - по элементам константного вектора. В теле первого создаем временный вектор, содержащий элементы основного. Организовать вложенный цикл для поиска слов во временном векторе. При нахождении слова - удалять его из вектора, устанавливать итератор в ноль и проходить заного до тех пор, пока не будет достигнут конец вектора или не закончатся подходящие слова. Полученные цепочки слов записывать в новый вектор.

Циклом пройтись по вектору полученных цепочек слов. Определить, являются ли они полными (последнее слово в цепочке - заключительное слово в условии задачи). Если не являются - удалить. Найти минимально короткую цепочку и вывести ее. Это и будет результат.

Спасибо за внимание.

0

Можете выложить свою программу??

0

Ну, элементарный поиск в ширину подойдет.

0