Дизайн и анализ на алгоритми 2010

"Това изглеждаше като толкова добра идея тази сутрин" - мислеше си Доктор Фордбелманов, взирайки се в листа изпод навъсени вежди.

"Евтино, лесно се започва, ще я занимава с дни... да бе! Кой ме би по главата да и' показвам 'Думинейшън', ама че съм глупав."

Думинейшън е следната игра:
Даден е речник от думи(в различните варианти на трудност, това са от 100 до 2000 думи). Те може, а може и да не са от някой истински тълковен речник. Но със сигурност няма да са по-дълги от 30 букви.
Дадена е някаква начална дума S.
Дадена е и крайна дума F.

На всеки ход върху текущата дума може да бъде извършвана една от следните операции:
Добавяне на буква.
Изтриване на буква.
Смяна на една буква с друга.

Освен това, задължително е да се получи нова дума, която също да е в речника.

Целта на играта е да се стигне от S до F. Печели този, който го направи с най-малко ходове.

Моля, помогнете на доктор Фордбелманов с играта, защото иначе ще му се наложи да загуби от седемгодишната си дъщеря Дийкстърка.

Напишете програма, която изписва думите през които се минава, за да се стигне от началната до крайната.
Тя трябва да приема 3 параметъра - име на файл, в което са думите, начална дума и крайна дума.

Пример:
words.txt abcd edg

(Съдържание на words.txt: )
abcd
edg
cccc
abcc
bdg
bcef
edg
abdc
bdc

Отговор:
abcd
abcc
abdc
bdc
bdg
edg


А за тези, които наистина искат да помогнат на добрия доктор - той може тайно тайно да добави още малко думи в речника.
Иска му се да знае с колко най-малко хода може да стигне от дума S до дума F *използвайки и думи, които ги няма в речника*.
Чувал е, че това има нещо общо с някой си Левенщайн, и е убеден, че още не сме го учили.
Затова предлага бонус един Сникерс. Или +1 единица в оценката за практикума по ДАА. Което си изберете.