Намиране на най-краткия път в лабиринт, Основи на програмирането
Раздели на сайта
Документация
Сайтове партньори
- януари 2016 (1)
- юни 2015 (1)
- Март, 2015 (1)
- май 2014 г. (1)
- април 2014 (1)
- януари 2013 г. (1)
- декември 2012 (1)
- май 2012 г. (3)
- април 2012 (3)
- Март 2012 (3)
- февруари 2012 (1)
- декември 2011 (1)
Намиране на най-краткия път в лабиринта
Задача: създайте програма, която намира път в лабиринта от началната точка до крайната точка, посещавайки всички специални точки на лабиринта Използван API: GTK/GDK; Среда за разработка: Dev-C++
Нека лабиринтът е даден като nxm матрица, всеки елемент от която казва дали има стена в тази клетка или не. Нека са дадени две точки: начало (зелено) и край (синьо), така че да е възможно да се премине от началната до крайната точка. Също така, нека са дадени k точки, които условно ще наречем "златни кюлчета", които са достъпни от началната точка. В този случай алгоритъмът за решение ще се състои от три части
1) намерете разстоянието между всички златни кюлчета и разстоянието от всяко златно кюлче до крайната точка. за това ще използваме алгоритъма за първо търсене в ширина
2) Използвайки динамично програмиране, ще намерим стойностите, необходими за изчисляване на отговора. Очакван брой операции 2 n * n 2
3.a) Извличане на дължина на пътя:
3.b) Начертаване на най-краткия път (пътят от последното златно кюлче до края се получава в обратен ред, т.е. от края до последното златно кюлче, за да не се предизвика още веднъж bfs):
Програмата има следните контроли: стрелки - придвижване през лабиринта k- показване на най-краткия път r - връщане на лабиринта в първоначалното му състояние.
Когато стартирате програмата, най-добрият възможен резултат в лабиринта се показва в конзолата. Веднага щом потребителят стигне до финалната линия, след като е събрал всички "златни кюлчета", неговият резултат ще бъде записан на конзолата.