Чуваська державний університет імені І. М. Ульянова.
Кафедра обчислювальної техніки.
Тема: В«Лабіринт. Генерація та пошук найкоротшого шляху В»
Роботу виконав:
студент групи
ІХТ-42-05
Тарасов Є.Е.
Керівник:
Васильєв Ю.Г.
Чебоксари 2006
1. Завдання
Лабіринт.
Написати програму знаходження найкоротшого шляху в лабіринті. Передбачити генерацію лабіринту і можливість вибору користувачем точки входу в лабіринт і точки виходу з нього. У програмі передбачити використання миші і розбиття на модулі. br/>
2. Функціональне призначення
Програма Labirint виконує ряд наступних операцій:
генерація лабіринту;
визначення користувачем точки входу в лабіринт і точки виходу з нього;
знаходження найкоротшого шляху від заданої користувачем точки входу в лабіринт до точки виходу і висновок шляху на екран або виведення на екран повідомлення про те, що не існує шляху між двома обраними користувачем локаціями.
3. Опис логічної структури
.1 Вибір способу вирішення завдання
Завдання може бути вирішена декількома способами:
1) організувати лабіринт з використанням запису:
У кожній локації лабіринту нас цікавить інформація про стінах/проходах. У локації може існувати від однієї до чотирьох стін (зверху, знизу, зліва і справа). Якщо значення поля одно true, значить, відповідна стіна існує, інакше - ні. p align="justify"> Насамперед, створимо заготовку - лабіринт з усіма можливими стінами. Далі підемо алгоритмом:
: = кількість локацій в лабіринті
ПОКИ locations> 1
вибираємо випадкову стіну в лабіринті
ЯКЩО не існує шляху між локаціями, розділеними цією стіною, розбиваємо стіну: = locations - 1
КІНЕЦЬ ЦИКЛУ
Знаходити шлях між точкою входу і виходу можна за алгоритмом методу хвильової трасування: Стартову локацію пометим одиницею (вилили кисіль). Тепер виконуємо дії. p align="justify"> Знайти в лабіринті локації, помічені одиницями для кожної з чотирьох сусідніх з нею локацій перевірити дві умови:
позначена чи вона нулем
чи є стіна між двома локаціями (обраної та сусідньої) якщо обидв...
