Пошук найкоротшого шляху в лабіринті

АНОТАЦІЯ
Метою представленої роботи є розробка програми "Пошук найкоротшого шляху", яка створює лабіринт і знаходить найкоротший шлях його проходження.
Програма призначена для використання у навчальних закладах, у пізнавальних цілях. Також можливе використання з метою самоперевірки.
У даній роботі наводяться діаграми потоків даних, діаграми стану, діаграми взаємодії модулів. Доступною мовою описується методологія створення програми.
Розроблено специфікація функцій програми, описано поведінку програми в критичних ситуаціях, наводиться специфікація модулів. У документації також наведені текст програми і результати тестування програми.

1 Технічне завдання
Введення
Повна назва розробки "Пошук найкоротшого шляху". Дана розробка призначена для використання в навчальних закладах. Вона виконує знаходження найкоротшого шляху між входом в лабіринт і його виходом. Також можливе використання для самоперевірки рішення, прийнятого людиною.
1.1 Підстави для розробки
Даний проект розробляється на підставі завдання на курсову роботу, виданого викладачем Сусловим С.В. студенту 4152 групи Заволока А.А.
Найменування теми розробки "Пошук найкоротшого шляху".
1.2 Призначення розробки
Програма "Пошук найкоротшого шляху" призначається для знаходження найкоротшого шляху між входом в лабіринт і його виходом.
1.3 Вимоги до програми
1.3.1 Вимоги до функціональних характеристик
Для контакту користувача з програмою необхідно виконання ряду функцій:
створення сітки лабіринту;
додавання кімнат у лабіринті;
видалення кімнат у лабіринті;
додавання дверей у лабіринті;
видалення дверей у лабіринті;
введення входу і виходу, між якими необхідно знайти найкоротший шлях;
відображення рішення;
збереження лабіринту;
- Завантаження збереженого лабіринту
Вхідними даними є кімнати та двері лабіринту, які вводяться користувачем з клавіатури за допомогою пересувається курсору і натиснення певної клавіші для кімнат і для дверей.
Вихідними даними є відображення на екрані в графічному режимі лабіринту і найкоротшого шляху.
1.3.2 Вимоги до надійності

Програмний виріб має бути захищене від непродуманих дій користувача. Повинен бути передбачений максимально можливий аналіз вхідної інформації, що вводиться користувачем. У разі введення некоректних даних ігнорувати спробу введення.

1.3.3 Умови експлуатації
Програма стійко і коректно функціонує при нормальних умовах експлуатації ПЕОМ. Додаткових умов експлуатації не вимагає.
1.3.4 Вимоги до складу і параметрів технічних засобів
Необхідні такі технічні засоби:
1) ПЕОМ з тактовою частотою процесора 100 Mhz і вище.
Монітор, що підтримує режим VGA;
8 Мбайт ОЗУ і вище;
Клавіатура.
     1.3.5 Вимоги до інформаційної та програмної сумісності
Програма повинна коректно функціонувати в ОС Windows'9x.
1.3.6 Вимоги до маркування та упаковки
Готове програмне виріб надається (зберігається) на дискеті 3.5 дюйма. Вимог до маркування не пред'являється.
1.3.7 Вимоги до транспортування та зберігання
Зберігати програмний продукт потрібно при нормальних умовах на дискеті 3.5 дюйма, тобто дискета повинна зберігатися в герметичній, сухий, не гнеться коробці далеко від джерел тепла, вологи і від магніту.
1.4 Вимоги до програмної документації
Програмна документація повинна складатися з:
добре прокоментованого тексту програми;
загального функціонального опису;
короткого опису складових програму функцій;
схем, що ілюструють проект і словесного їх опису;
5) керівництва користувача.

1.5 Техніко-економічні показники
Створення безкоштовної альтернативи існуючим на сьогодні програм подібного профілю;
Швидкість обчислень.
1.6 Стадії та етапи розробки
Технічне завдання
Планові терміни початку і закінчення роботи:
Початок: 15.02.07
Закінчення: 01.03.07
Ескізний проект
Планові терміни початку і закінчення роботи:
Початок: 01.03.07
Закінчення: 22.03.07
Технічний проект
Планові терміни початку і закінчення роботи:
Початок: 22.03.07
Закінчення: 12.04.07
Робочий проект
Планові терміни початку і закінчення роботи:
Початок: 12.04.07
Закінчення: 17.05.07
Введення в експлуатацію
Планові терміни початку і закінчення роботи:
Початок: 17.05.07
Закінчення: 24.05.07
1.7 Порядок контролю та приймання
Випробовування повинні проводитися спільно із замовником і розробником відповідно до "Програми і методики випробувань".
2. Ескізний проект
2.1 Контекстна діаграма
Вхідними даними повинні бути координати вершин багатокутника. Координати раціональніше не вводити, тому що це буде дуже тривалий процес, а змоделювати програму так щоб користувач міг переміщати курсор по сітці лабіринту і натисканням клавіш розставляти кімнати або двері. Вихідними даними є зображення лабіринту і результат пошуку шляху. Потоки вхідних і вихідних даних можна побачити на контекстній діаграмі.
При роботі з цією програмою необхідно наявність трьох головних компонентів: користувач, комп'ютер і програма (рис.2.1).

лабіринт

§ Користувач

Жорсткий диск

Програма

дані редагування

лабіринт

§ Результат

Малюнок 2.1 - Контекстна діаграма
Користувач отримує від програми результат - найкоротший шлях у лабіринті, який вийшов після обробки введених даних - координат дверей та кімнат. Результат програми при необхідності може бути збережений.
2.2 Словник даних
Лабіринт - безліч кімнат, з'єднаних між собою дверима.
Кімната - символічно зображений квадрат, заданий в лабіринті.
Двері-пристрій, що з'єднує кімнати.
Дані редагування - зміна лабіринту, тобто введення кімнат і дверей, а також їх видалення.
Результат - Найкоротший шлях у лабіринті.

2.3 Діаграма станів

0

1

4

3_

5

2

6

72

Малюнок 2.3 - Діаграма станів
Стан 0 - завантаження програми - початковий стан, в якому знаходиться програма після завантаження. У цьому стані користувач може ознайомитися з керуванням або вийти з програми.
Стан 1 - створення лабіринту - стан, в якому формується лабіринт.
Стан 2 - введення кімнати - в цьому стані користувач може ввести кімнату.
Стан 3 - введення двері - у цьому стані користувач може ввести двері.
Стан 4 - видалення кімнати - в цьому стані користувач (при необхідності) може видалити існуючу кімнату.
Стан 5 - видалення двері - у цьому стані користувач (при необхідності) може видалити існуючу двері.
Стан 6 - збереження лабіринту - користувачеві надається можливість зберегти лабіринт.
Стан 7 - завантаження лабіринту - користувачеві надається можливість завантажити, раніше збережений, лабіринт.
2.4 Побудова моделі для користувача інтерфейсу
Для зручності введення, редагування та видалення елементів лабіринту, необхідно створити зручний, дружній інтерфейс.
При запуску програми на екрані з'являється сітка, в якій буде вводитися лабіринт. У кожній клітинці може перебувати кімната або двері. По сітці пересувається курсор, який управляється за допомогою клавіш < > - Вгору, < > - Вниз, < > - Вправо, < > - Вліво він визначає положення кімнати або двері. На екрані постійно присутнє меню підказки, яке допомагає користувачеві орієнтуватися. У ньому вказується клавіші, за допомогою яких користувач може задати лабіринт. Наприклад, за допомогою клавіші <до> відбувається введення кімнати, при цьому кімната відображається у вигляді точки зеленого кольору, за допомогою клавіші <д> відбувається введення двері, яка не малюється а просто з'єднує кімнати і являє собою дві перехресні лінії, тобто можна з'єднувати відразу кілька дверей у кімнатах і малювати лабіринт у трьох або в чотирьох напрямках. За допомогою клавіші <я> можна редагувати лабіринт тобто видаляти вершини або ребра.
Після введення лабіринту в лівому верхньому кутку екрана видається запрошення: "Введіть вхід в лабіринт" після чого очікується вибір однієї з кімнат у лабіринті, за допомогою клавіш управління курсром і клавіші <Enter>, при цьому видається піглашеніе: "Введіть вихід з лабіринту". Після вибору виходу програма видає повідомлення: "Найкоротший шлях знайдений" - у тому випадку, якщо він знайдений або "шляху немає" - якщо шляху не існує. Якщо найкоротший шлях знайдений, то він буде показаний на графі у вигляді підсвічування червоним кольором. Далі пропонується вийти з програми шляхом натискання клавіші <Esc> або почати введення нового лабіринту натиснувши при цьому будь-яку клавішу. При цьому існує клавіша <c> і <з> відповідно для збереження лабіринту чи завантаження вже існуючого.

3 Технічний проект
3.1 Діаграма потоків даних
Програма має 4 основні процеси, що відображають основні функції програми:

1 Введення лабіринту та його редагування

2 Пошук шляху

3 Зчитування і Збереження файлу

Координати кімнат і дверей

§ карта поля

§ § Карта проходження

§ карта поля

§ карта поля

4 Відображення

Малюнок 3.1 - Діаграма 1-го рівня

Команди:
завантаження лабіринту
збереження лабіринту
створення кімнати
створення двері
видалення кімнати або двері
вихід
3.5 Розробка структури програми
Виходячи з вимог до програми, раціональніше всього розділити її на модулі, взаємодія яких показано на малюнку 3.5.1

Малюнок 3.5.1 - Взаємодія модулів

Введення команд

Модуль введення і коректування вхідних даних

Модуль розрахунку найкоротшого шляху лабіринту

Модуль збереження і зчитування структури лабіринту

Файли з структурою лабіринту

Графічне відображення

Модуль візуалізації

Модуль створення і промальовування сітки лабіринту

3.6 Специфікація модулів
Модуль створення і промальовування сітки лабіринту
Вхідні дані: відсутні
Вихідні дані: карта поля
Функції: створення карти поля
Модуль введення і коректування даних
Вхідні дані: команди
Вихідні дані: карта поля
Функції - введення даних і надання користувачеві можливості їх редагування.
Модуль зчитування і збереження структури лабіринту
Вхідні дані: команди, карта поля
Вихідні дані: карта поля, файл
Зовнішні ефекти: завантаження збереженого лабіринту, також модуль зберігає файл на диску.
Функції - зчитування і збереження структури лабіринту.
Модуль візуалізації
Вхідні дані: координати кімнат і дверей
Вихідні дані: відсутні
Зовнішні ефекти: на екрані монітора з'являється лабіринт і шлях проходження.
Функції - висновок на екран монітора інформації.
Модуль розрахунку найкоротшого шляху лабіринту
Вхідні дані: карта поля
Вихідні дані: карта проходження
Функції - знаходження шляхів проходження і пошук найкоротшого.
3.7 Перехід до тексту програми
Використовуючи матеріал розробки програми, діаграму потоків даних, діаграму станів перейдемо до реалізації програми.
Написання програмного коду буде проводитися з використанням середовища програмування Borland C + +.
Реалізація функцій програми залежить повністю від програміста.

4 Робочий проект
4.1 Програмування та налагодження програми
Виходячи з вимог до програмного забезпечення, програма кодувалася в середовищі програмування Borland C + + для функціонування в операційній системі Windows 9x. (Дивіться додаток В)
4.2 Тестування програми
Тестування програми полягає у перевірці роботи основних функцій. Була розроблена і проведена серія тестових прикладів для програми. Програма та методика випробувань наведені в додатку В. Результати тестування показали працездатність програми і його відповідність пропонованим вимогам.
Запропоноване ПО тестувалося як під час розробки, так і після її завершення.
Для тестування робилися спроби введення недійсних даних і спроби виконати неприпустимі дії як при програмуванні, так і в режимі взаємодії з користувачами. Запропоноване ПО адекватно реагувало на такі дії.

Висновок
У даній документації була розроблена програма "Пошук найкоротшого шляху", яка створює лабіринт і знаходить найкоротший шлях проходження.
Описана область застосування програмного продукту. Наводяться діаграми потоків даних, діаграми стану, діаграми взаємодії модулів. Доступною мовою описується методологія створення програми.
Розроблено специфікація функцій програми, описано поведінку програми в критичних ситуаціях, наводиться специфікація модулів. У документації також наведені результати тестування програми
ДОДАТОК А
(Обов'язковий)
Опис програми
Загальні відомості
Найменування програми: "Пошук найкоротшого шляху"
Для функціонування програми необхідна операційна система Windows 9x.
Кодування проводилася в середовищі програмування Borland C + +.
Функціональне призначення
Класи завдань, які вирішуються за допомогою програми: програма знаходить найкоротший шлях у лабіринті.
Опис логічної структури
Програма має головну функцію main, яка описана у файлі sapr_kyrsovik.cpp, з якої починається виконання програми. Також програма має бібліотечні функції, які описані в заголовному файлі head.h. Заголовний файл містить всі інші функції, які використовуються в пограми. Програма має структуру з ім'ям Lab, яка містить двовимірний масив карти лабіринту (березень [MY] [MX]) і двомірний масив карти проходження (Put [MY] [MX]). У цю структуру проводиться запис координат кімнат і дверей лабіринту.
Програма складається з таких функцій:
int Grin (struct Lab * P)
Вона виконує:
ініціалізацію графіки: очищається екран, включається графічний режим
малює сітку лабіринту
ініціалізацію масивів структури P
void Rasstan (struct Lab * P) - функція розставляє кімнати та двері на карті поля, а також видаляє їх, це реалізується за допомогою клавіш управління курсором (< > - Вгору, < > - Вниз, < > - Вправо, < > - Вліво) і клавіш спеціального призначення (наприклад, за допомогою клавіші <до> відбувається введення кімнати, за допомогою клавіші <д> відбувається введення двері, за допомогою клавіші <я> можна видаляти кімнати або двері). Ця функція викликає додаткові дві функції:
void vyvod (int x, int y) - функція малює рамочку білого кольору, що служить курсором для розстановки і видалення кімнат і дверей а також служить для введення входу і виходу в лабіринті.
void maska ​​(int x, int y) - функція приховує (зафарбовує) курсор.

void Vvod (struct Lab * P, int * x1, int * y1, int * x2, int * y2) - функція запитує ввести вхід в лабіринт, після чого за допомогою клавіш управління курсором та клавіші Enter функція зчитує вхід, далі функція запитує ввести вихід.

int Find (struct Lab * P, int x1, int y1, int x2, int y2) - виконує пошук шляху.
void Puty (struct Lab * P, int x1, int y1, int x2, int y2) - функція промальовує шлях.
Використовувані технічні засоби
 
Необхідні такі технічні засоби:
486 DX-4 100 MHz процесор і вище;
8 Мб ОЗУ і вище;
Монітор, миша і клавіатура.
Виклик і завантаження
Виклик програми здійснюється за допомогою запуску файлу sapr_kyrsovik.exe. Програма займає 40 байт.
Вхідні дані
Вхідними даними є кімнати та двері, які вводяться шляхом натискання клавіш спеціального призначення:
щоб ввести кімнату необхідно натиснути клавішу <до>;
щоб ввести двері необхідно натиснути клавішу <д>;
щоб видалити кімнату або двері необхідно натиснути клавішу <я>.

Вихідні дані
Вихідними даними є відображення введеного лабіринту, тобто відображення кімнат і дверей, а також відображення знайденого найкоротшого шляху в лабіринті, і в разі збереження - файл.

ДОДАТОК Б
(Довідковий)
Опис застосування
Призначення програми
Програма "Пошук найкоротшого шляху" знаходить найкоротший шлях у лабіринті.
Умови застосування
Необхідні такі технічні засоби:
1) 486 DX4 100 процесор і вище;
8 Мбайта ОЗУ і вище;
Монітор, Клавіатура.
Програма призначена для роботи в ОС Windows 9x.
Опис завдання
Програма "Пошук найкоротшого шляху" знаходить найкоротший шлях у лабіринті.
Вхідні і вихідні дані
Вхідні дані:
Вхідними даними є кімнати та двері, які вводяться шляхом натискання клавіш спеціального призначення:
щоб ввести кімнату необхідно натиснути клавішу <до>;
щоб ввести двері необхідно натиснути клавішу <д>;
щоб видалити кімнату або двері необхідно натиснути клавішу <я>.
Вихідні дані:
Вихідними даними є відображення введеного лабіринту, тобто відображення кімнат і дверей, а також відображення знайденого найкоротшого шляху в лабіринті, і в разі збереження - файл.

Додаток В.
(Обов'язковий)
Програма та методика випробувань

Об'єкт випробувань
Об'єктом випробувань є програма "Пошук найкоротшого шляху", яка призначена для знаходження найкоротшого шляху в лабіринті.
Мета випробувань
Метою проведення випробувань є перевірка працездатності розроблених функцій програмного забезпечення, а також перевірка відповідності завдань, реалізованих у програмі з тими, які були поставлені замовником.
Вимоги до програми
    
     Під час випробувань необхідно перевірити відповідність вимог на програму, зазначених у "Технічному завданні", а саме:
1) "Вимоги до функціональних характеристик";
2) "Вимоги до надійності";
3) "Вимоги до складу і параметрів технічних засобів";
4) "Вимоги до інформаційній та програмної сумісності".
Вимоги до програмної документації
На випробування повинен бути пред'явлений наступний склад програмної документації:
текст програми;
програма і методика випробувань;
опис програми;
опис застосування;

Засоби і порядок випробувань
Випробування будуть проводитися в кілька етапів. Перший етап - перевірка правильності роботи окремих модулів програми. Другий етап - перевірка роботи всіх модулів разом.
Випробування повинні проходити при таких технічних і програмних засобах:
486 DX4 100 процесор і вище;
8 Мбайта ОЗУ і вище;
Монітор, Клавіатура.
Програмне забезпечення: оболонка Borland C 3.1.
Методи випробувань
При випробуванні програми буде використовуватися стратегія "чорного ящика" зокрема наступні методи:
еквівалентне розбиття;
припущення про помилку;
Еквівалентна розбивка:
1) Для неправильного класу еквівалентності необхідно перевірити наступні тести:
ввести клавіші 'g', 'd', 'v', ... 1, 2, 3, ....
Результат: програма не ріагірует на введені клавіші.
2) Для правильного класу еквівалентності необхідно перевірити наступні тести:
ввести клавіші 'до', 'д'
Результат: на моніторі відображаються кімнати та двері.
Припущення про помилку
Для функції «Rasstan», випробування необхідно проводити за методом «Припущення про помилку». Для випробування даної функції необхідно виконати наступні дії:
Перевірка № 1:
Натиснути клавішу <до>;
Результат: На екрані з'явилася точка, яка позначає кімнату.
Перевірка № 2:
Натиснути клавішу <д>;
Результат: На екрані з'явився відрізок, що позначає двері.
Перевірка № 3:
Натиснути клавішу <я>, на кімнаті;
Результат: Зображення кімнати зникло, а на його місці буде порожньо.
Для функції «Vvod», випробування необхідно проводити за методом «Припущення про помилку». Для випробування даної функції необхідно виконати наступні дії:
Перевірка № 1:
При запиті входу в лабіринт натиснути клавішу <enter> на порожньому місці;
Результат: Нічого не відбудеться
Перевірка № 2:
При запиті виходу з лабіринту натиснути клавішу <enter> на двері;
Результат: Нічого не відбудеться
Перевірка № 3:
При запиті входу в лабіринт натиснути клавішу <enter> на кімнаті;
Результат: Програма попросить ввести вихід.
Тести для програми:
1) ввести окремо стоять, не пов'язані кімнати і ввести вхід і вихід. Програма видає результат
Результат: Шлях не знайдено.
2) ввести правильний лабіринт знайти шлях між входом і виходом. Програма видає результат
Результат: Найкоротший шлях знайдений.

Випробування за методом "білого ящика":
Для тестування вирішено застосувати покрокове тестування зверху вниз (низхідний), при якому тестування починається з верхнього, головного модуля програми, причому модулі будуть тестуватися не ізольовано один від одного, а підключатися по черзі для виконання тесту до набору вже раніше відтестовані модулів.
Тестований модуль:
void Rasstan (struct Lab * P)
{
int x = 1, y = 1;
char a;
do {
a = getch ();
if (! a) a = getch ();
switch (a)
{
case 80: if (y <MY) + + y; break;
case 72: if (y> 1) - y; break;
case 75: if (x> 1) - x; break;
case 77: if (x <MX) + + x; break;
case 'z': P-> Map [y] [x] = 0;
break;
case 'x': P-> Map [y] [x] = 1;
break;
case 'c': P-> Map [y] [x] = 2;
break;
case 27: exit (0);
}
} While (a! = 13);
}
Цей модуль повинен отримувати карту поля зі структури лабіринту, створимо її.

Ø Для цього модуля маємо наступні тести (Таблиця 1):

Таблиця 1 - Тести для модуля Rasstan

№ тесту	Дія	Подія	Відповідність
§ § Критерій тестування: покриття рішень
1	Натиснути клавішу <↑> (Вгору)	курсор перемістився вгору	повне відповідність
2	Натиснути клавішу <↓> (Вниз)	курсор перемістився вниз	повне відповідність
3	Натиснути клавішу <←> (Ліворуч)	курсор перемістився вліво	повне відповідність
4	Натиснути клавішу <→> (Вправо)	курсор перемістився вправо	повне відповідність
5	ввести клавішу'х ' (Ребро)	на карті поля відобразилось значення "1"	повне відповідність
6	ввести клавішу'с ' (Вершину)	на карті поля відобразилось значення '2 '	повне відповідність
7	навести курсор на значеніе'1'ілі'2 'і ввести клавішу'z ' (Т.е.удаліть)	на карті поля відобразилось значення "0" замість значенія'2'ілі'1 '	повне відповідність
8	Натиснути клавішу'Esc '	вихід з програми	повне відповідність
Критерій тестування: покриття умов
9	Натиснути клавішу <↑> (Вгору) і пересувати курсор до тих пір, поки не досягне кордону	§ Курсор не виходить за межі поля	повне відповідність
10	Натиснути клавішу <↓> (Вниз) і пересувати курсор до тих пір, поки не досягне кордону	§ Курсор не виходить за межі поля	повне відповідність
11	Натиснути клавішу <←> (Ліворуч) і пересувати курсор до тих пір, поки не досягне кордону	§ Курсор не виходить за межі поля	повне відповідність
12	Натиснути клавішу <→> (Праворуч) і пересувати курсор до тих пір, поки не досягне кордону	§ Курсор не виходить за межі поля	повне відповідність

Модуль, що тестується:
void Vvod (struct Lab * P, int * x1, int * y1, int * x2, int * y2)
{
gotoxy (3,2); printf ("Введіть вхід в лабіринт");
int x = 1, y = 1;
char a;
do {
a = getch ();
if (! a) a = getch ();
CursorHide (x, y);
switch (a) {
case 80: if (y <MY) + + y; break;
case 72: if (y> 1) - y; break;
case 75: if (x> 1) - x; break;
case 77: if (x <MX) + + x; break
case 27: exit (0);
}
if ((a == 13) & & (P-> Map [y] [x] == 2)) break;

} While (1);
* X1 = x; * y1 = y;
gotoxy (3,4); printf ("Введіть вихід з лабіринту");
do {0
a = getch ();
if (! a) a = getch ();
switch (a) {
case 80: if (y <MY) + + y; break;
case 72: if (y> 1) - y; break;
case 75: if (x> 1) - x; break;
case 1977: if (x <MX) + + x; break;
case 27: exit (0);
}
if ((a == 13) & & (P-> Map [y] [x] == 2)) break;
} While (1);
* X2 = x; * y2 = y;
gotoxy (3,5); printf ("x2 =% 3i y2 =% 3i", x, y);
}

Ø

Ø Для цього модуля маємо наступні тести (Таблиця 2):

Таблиця 2 - Тести для модуля Vvod

№ тесту	Дія	Передбачуване поведінку Функції	Відповідність
§ § Критерій тестування: покриття рішень
1	Натиснути клавішу <↑> (Вгору)	курсор повинен переміститися вгору	повне відповідність
2	Натиснути клавішу <↓> (Вниз)	курсор повинен переміститися вниз	повне відповідність
3	Натиснути клавішу <←> (Ліворуч)	курсор повинен переміститися вліво	повне відповідність
4	Натиснути клавішу <→> (Вправо)	курсор повинен переміститися вправо	повне відповідність
5	Натиснути клавішу'Esc '	вихід з програми	повне відповідність
Критерій тестування: покриття умов
6	Натиснути клавішу <↑> (Вгору) і пересувати курсор до тих пір, поки не досягне кордону	§ Курсор не повинен виходити за межі поля	повне відповідність
7	Натиснути клавішу <↓> (Вниз) і пересувати курсор до тих пір, поки не досягне кордону	§ Курсор не повинен виходити за межі поля	повне відповідність
8	Натиснути клавішу <←> (Ліворуч) і пересувати курсор до тих пір, поки не досягне кордону	§ Курсор не повинен виходити за межі поля	повне відповідність
9	Натиснути клавішу <→> (Праворуч) і пересувати курсор до тих пір, поки не досягне кордону	§ Курсор не повинен виходити § за межі поля	повне відповідність
10	навести курсор на двері і натиснути Enter	§ Функція не буде реаг- § ровать на введення	повне відповідність
11	навести курсор на кімнату і натиснути Enter	Функція має попроси ть ввести вихід з лаби Рінта.	повне відповідність

Модуль, що тестується:
int Find (struct Lab * P, int x1, int y1, int x2, int y2)
{
int x, y, k = 1, F = 1;
P-> Put [y2] [x2] = k;
while (F)
{
F = 0;
for (x = 1; x <= MX; x + +)
{
for (y = 1; y <= MY; y + +)
{
if (P-> Put [y] [x] == k)
{
if (P-> Map [y +1] [x]! = 0 & & P-> Put [y +1] [x] == 0)
{P-> Put [y +1] [x] = k +1; F = 1;}
if (P-> Map [y-1] [x]! = 0 & & P-> Put [y-1] [x] == 0)
{P-> Put [y-1] [x] = k +1; F = 1;}
if (P-> Map [y] [x +1]! = 0 & & P-> Put [y] [x +1] == 0)
{P-> Put [y] [x +1] = k +1; F = 1;}
if (P-> Map [y] [x-1]! = 0 & & P-> Put [y] [x-1] == 0)
{P-> Put [y] [x-1] = k +1; F = 1;}
}
}
}
k + +;
}
if (P-> Put [y1] [x1] == 0)
{
gotoxy (3,7); printf ("Шлях не знайдено");
}
else
{
gotoxy (3,7); printf ("Найкоротший шлях знайдений");
}
У модуль повинна передаватися карта поля і координати двох вершин х1, y1
і х2, y2 отримані від функції Vvod, між якими необхідно знайти
найкоротший шлях.

Ø Для цього модуля маємо наступні тести (Таблиця 3):

Таблиця 3 - Тести для модуля Find

№ тесту	Дія	Передбачуване поведе- ня функції	Відповідність
§ § Критерій тестування: покриття рішень / умов
1	Необхідно сформували- ровать лабіринт і ввести дві вершини, між якими необхідно знайти найкоротший шлях	функція повинна знайти шлях і видати відповідне повідомлення	повне відповідність
2	Необхідно сформували- ровать не пов'язані лабіринт і ввести 2 вершини, між якими необхід- мо знайти шлях	функція не повинна знайти шлях і видати відпо- вующие повідомлення	повне відповідність

Текст програми
# Include <d:\4term\bc\bin\suslov\head.h>
void main ()
{
static struct Lab P;
int X1, X2, Y1, Y2;
char a;
do {
Grin (& P);
/ / Q (& P);
Rasstan (& P);
Vvod (& P, & X1, & Y1, & X2, & Y2);
if (! Find (& P, X1, Y1, X2, Y2))
{
gotoxy (3,7); printf ("Шлях не знайдено");
}
else
{
gotoxy (3,7); printf ("Найкоротший шлях:");
Puty (& P, X1, Y1, X2, Y2);
}
/ / Q (& P);
gotoxy (3,8); printf ("Press Esc to exit or any key to continue");
a = getch ();
} While (a! = 27);
closegraph ();
}
Заголовний файл:
# Include <conio.h>
# Include <stdio.h>
# Include <stdlib.h>
# Include <graphics.h>
# Include <dos.h>
const
SX = 10, / / ​​координати початку
SY = 130, / /
MX = 30, / / ​​Колві клітин по осях
MY = 17,
R = 20,
SetkaColor = DARKGRAY,
RebroColor = GREEN,
UzelColor = GREEN,
CursorColor = 15,
PutColor = RED;
struct Lab
{
int Map [MY +2] [MX +2];
/ / Карта лаб 0-непроходимо 1-двері 2-кімната
int Put [MY +2] [MX +2];
/ / Карта проходження 1-непрохідний
};
int Grin (struct Lab * P)
{
int gdriver = DETECT, gmode, errorcode;
initgraph (& gdriver, & gmode ,"");
errorcode = graphresult ();
if (errorcode! = grOk)
{
printf ("Graphics error:% s \ n", grapherrormsg (errorcode));
printf ("Graphics error: Press any key:");
getch ();
exit (1);
};
int x, y;
for (y = 0; y <MY +2; y + +)
for (x = 0; x <MX +2; x + +)
{
P-> Map [y] [x] = 0; / * ініціалізує масиви * /
P-> Put [y] [x] = 0;
}
for (y = 0; y <MY +2; y + +)
{
P-> Put [y] [0] =- 1;
P-> Put [y] [MX +1] =- 1;
}
for (x = 0; x <MX +2; x + +)
{
P-> Put [0] [x] =- 1;
P-> Put [MY +1] [x] =- 1;
}
/ / Setka
setcolor (SetkaColor);
for (y = 0; y <= MY; y + +)
for (x = 0; x <= MX; x + +)
{
line (SX + x * R, SY, SX + x * R, SY + R * MY);
line (SX, SY + y * R, SX + MX * R, SY + y * R);
}
return 0;
}
void maska ​​(int x, int y)
{
setcolor (0);
rectangle (SX + (x-1) * R +1, SY + (y-1) * R +1, SX + x * R-1, SY + y * R-1);
}
void vyvod (int x, int y)
{
setcolor (CursorColor);
rectangle (SX + (x-1) * R +1, SY + (y-1) * R +1, SX + x * R-1, SY + y * R-1);
}
void Rasstan (struct Lab * P)
{
int x = 1, y = 1; / / Коорти курсору
gotoxy (55,4); printf ("Керування:");
gotoxy (55,5); printf ("я - видалити");
gotoxy (55,6); printf ("д - двері");
gotoxy (55,7); printf ("до - кімната");
gotoxy (55,8); printf ("Enter - запровадити");
vyvod (x, y);
char a;
do {
a = getch ();
if (! a) a = getch ();
maska ​​(x, y);
switch (a)
{
case 80: if (y <MY) + + y; break; / * вниз * /
case 72: if (y> 1) - y; break; / * вгору * /
case 75: if (x> 1) - x; break; / * вліво * /
case 77: if (x <MX) + + x; break; / * вправо * /
case 'z': P-> Map [y] [x] = 0;
setcolor (0); setfillstyle (1,0);
bar (SX + (x-1) * R +1, SY + (y-1) * R +1, SX + x * R-1, SY + y * R-1);
break;
/ / Розставляти ком і дв
case 'l': P-> Map [y] [x] = 1;
setcolor (RebroColor);
line (SX + x * RR / 2, SY + (y-1) * R +1, SX + x * RR / 2, SY + y * R-1);
line (SX + (x-1) * R +1, SY + y * RR / 2, SX + x * R-1, SY + y * RR / 2);
break;
case 'r': P-> Map [y] [x] = 2;
setcolor (UzelColor); setfillstyle (1, UzelColor);
fillellipse (SX + x * RR / 2, SY + y * RR / 2, R/2-1, R/2-1);
break;
case 27: exit (0); / / vixod iz programmi
}
vyvod (x, y);
} While (a! = 13);
maska ​​(x, y);
}
void Vvod (struct Lab * P, int * x1, int * y1, int * x2, int * y2)
{
gotoxy (3,2); printf ("Введіть вхід в лабіринт");
int x = 1, y = 1;
char a;
vyvod (x, y);
do {
a = getch ();
if (! a) a = getch ();
maska ​​(x, y);
switch (a) {
case 1980: if (y <MY) + + y; break; / * вниз * /
case 72: if (y> 1) - y; break; / * вгору * /
case 75: if (x> 1) - x; break; / * вліво * /
case 77: if (x <MX) + + x; break; / * вправо * /
case 27: exit (0);
}
vyvod (x, y);
if ((a == 13) & & (P-> Map [y] [x] == 2)) break;
} While (1);
maska ​​(x, y);
* X1 = x; * y1 = y;
gotoxy (3,3); printf ("x1 =% 3i y1 =% 3i", x, y);
gotoxy (3,4); printf ("Введіть вихід");
vyvod (x, y);
do {
a = getch ();
if (! a) a = getch ();
maska ​​(x, y);
switch (a) {
case 80: if (y <MY) + + y; break; / * вниз * /
case 72: if (y> 1) - y; break; / * вгору * /
case 75: if (x> 1) - x; break; / * вліво * /
case 77: if (x <MX) + + x; break; / * вправо * /
case 27: exit (0);
}
vyvod (x, y);
if ((a == 13) & & (P-> Map [y] [x] == 2)) break;
} While (1);
maska ​​(x, y);
* X2 = x; * y2 = y;
gotoxy (3,5); printf ("x2 =% 3i y2 =% 3i", x, y);
}
int Find (struct Lab * P, int x1, int y1, int x2, int y2)
{
int x, y, k = 1, F = 1;
P-> Put [y2] [x2] = k;
while (F)
{
F = 0;
for (x = 1; x <= MX; x + +)
{
for (y = 1; y <= MY; y + +)
{
if (P-> Put [y] [x] == k)
{
if (P-> Map [y +1] [x]! = 0 & & P-> Put [y +1] [x] == 0)
{P-> Put [y +1] [x] = k +1; F = 1;}
if (P-> Map [y-1] [x]! = 0 & & P-> Put [y-1] [x] == 0)
{P-> Put [y-1] [x] = k +1; F = 1;}
if (P-> Map [y] [x +1]! = 0 & & P-> Put [y] [x +1] == 0)
{P-> Put [y] [x +1] = k +1; F = 1;}
if (P-> Map [y] [x-1]! = 0 & & P-> Put [y] [x-1] == 0)
{P-> Put [y] [x-1] = k +1; F = 1;}
}
}
}
k + +;
}
if (P-> Put [y1] [x1] == 0) return 0; else return 1;
}
void Puty (struct Lab * P, int x1, int y1, int x2, int y2)
{
int x = x1, y = y1;
int k;
setcolor (PutColor);
setfillstyle (1, PutColor);
while (! (x == x2 & & y == y2))
{
fillellipse (SX + x * RR / 2, SY + y * RR / 2, R / 4, R / 4);
k = P-> Put [y] [x] -1;
if (P-> Put [y +1] [x] == k) {y + +; continue;}
if (P-> Put [y-1] [x] == k) {y -; continue;}
if (P-> Put [y] [x +1] == k) {x + +; continue;}
if (P-> Put [y] [x-1] == k) {x -; continue;}
}
fillellipse (SX + x * RR / 2, SY + y * RR / 2, R / 4, R / 4);
}
ДОДАТОК Г

§ Керівництво користувача

П.1. Призначення програми
Програма "Пошук найкоротшого шляху" призначена для знаходження найкоротшого шляху в лабіринті. Програма призначена для використання у навчальних закладах, у пізнавальних цілях. Також можливе використання з метою самоперевірки.
П.2. Умови експлуатації програми
Для того, щоб працювати з даною програмою вам необхідно мати персональний комп'ютер (мінімум 486) з 8 МБ ОЗУ і звичайно операційну систему Windows 9x.
П.3. Виконання програми
Порядок дій, що забезпечує запуск програми:
- Завантажити операційну систему Microsoft Windows9x
- Якщо Вам не вдалося завантажити операційну систему Microsoft
Windows 9x або у Вас немає операційної системи Microsoft Windows 9x,
то зверніться у відділ технічної підтримки корпорації Microsoft для
отримання відповідних інструкцій. (Електронна адреса відділу
технічної підтримки:
megabug_company_tech_department@microsoft.com)
- Запустити на виконання файл sapr_kyrsovik.exe з директорії, в якій він розташований.
- Після запуску програми на екрані монітора можна ознайомитися з керуванням програми.
- Клавішами управління слід розставити двері та кімнати в лабіринті, після чого ввести вхід і вихід з лабіринту.
- Почекати поки програма видасть результат і вийти з програми або почати створення нового лабіринту.
- Для того, щоб завершити роботу з програмою необхідно натиснути <esc> в будь-який момент виконання програми.