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

Здравейте, по време на упражненията се уговорихме да кача решения на задачите, затова сега - с лееко закъснение - правя именно това.

Няколко уговорки:
Възможно е в някои (визуални кхъ-кхъ) редактори коментарите на кирилица да не се четат. Кодирането, доколкото помня, е UTF-8. Ако всичко друго се провали, преименувайте ги на .txt и ги отворете във Firefox. След това си вземете по-хубав редактор :)
Програмите имат може би твърде много коментари(с образователна цел). Гледайте да не си помислите, че и вие трябва да пишете така :)


Относно втора задача:
Разбрах, че някои хора са имали проблеми с новите редове. Входните данни са генерирани под Линукс, така че това е напълно възможно. За да нямате болежки с това вбъдеще, гледайте да ползвате стандартните средства за четене на вход - scanf/cin се грижат вместо вас за такива дребни неща. read/fread - не.

Моето решение на втора задача е бързо, но има и още по-бързо.





Относно трета задача:
Печелившият път се намира като пуснем по един BFS за всяко извънземно, както и за Гордън. Вземаме квадратчетата, до които Гордън може да стигне преди извънземните. От всички такива вземаме това, в което извънземните стигат най-късно.
Лесно се доказва, че винаги съществува път до това квадратче(с допускане на противното), а BFS-ът ни дава точно как се стига дотам. Щом застане където трябва, Гордън стои и чака до края.

Пращам програмка, с която да си тествате решенията. Тя е написана на Python, защото там лесно може да се подкара някаква графика(съответно, показва ви точно кога, къде и как ще ви изпапкат извънземните).

Има упътване в какъв формат са входните данни.
Ако го тествате с име на файл "lalala", ще отидете в cheat mode и ще ви покаже оптималния път.
Използвайте стрелките, за да движите времето напред-назад.

Python не е бърз език. За лабиринти над 50*50 вече започва да се усеща забавяне.
На C/C++ трябва да можете да решите 1000*1000 лабиринт с 10 извънземни за секунда-две.

Ще ви трябват Python2.6 и Pygame:
http://www.python.org/download/
http://www.pygame.org/download.shtml