Курсовая работа: Поиск кратчайшего пути в лабиринте

АННОТАЦИЯ

Целью представленной работы является разработка программы “Поиск кратчайшего пути”, которая создает лабиринт и находит кратчайший путь его прохождения.

Программа предназначена для использования в учебных заведениях, в познавательных целях. Также возможно использование в целях самопроверки.

В данной работе приводятся диаграммы потоков данных, диаграммы состояния, диаграммы взаимодействия модулей. Доступным языком описывается методология создания программы.

Разработана спецификация функций программы, описано поведение программы в критических ситуациях, приводится спецификация модулей. В документации также приведены текст программы и результаты тестирования программы.

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 Диаграмма состояний

Рисунок 2.3 – Диаграмма состояний

Состояние 0 – загрузка программы – начальное состояние, в котором находится программа после загрузки. В этом состоянии пользователь может ознакомиться с управлением или выйти из программы.

Состояние 1 – создание лабиринта – состояние, в котором формируется лабиринт.

Состояние 2 – ввод комнаты – в этом состоянии пользователь может ввести комнату.

Состояние 3 – ввод двери – в этом состоянии пользователь может ввести дверь.

Состояние 4 – удаление комнаты – в этом состоянии пользователь (при необходимости) может удалить существующую комнату.

Состояние 5 – удаление двери – в этом состоянии пользователь (при необходимости) может удалить существующую дверь.

Состояние 6 – сохранение лабиринта – пользователю предоставляется возможность сохранить лабиринт.

Состояние 7 – загрузка лабиринта – пользователю предоставляется возможность загрузить, ранее сохраненный, лабиринт.

2.4 Построение модели пользовательского интерфейса

Для удобства ввода, редактирования и удаления элементов лабиринта, необходимо создать удобный, дружественный интерфейс.

При запуске программы на экране появляется сетка, в которой будет вводиться лабиринт. В каждой клеточке может находиться комната или дверь. По сетке передвигается курсор, который управляется с помощью клавиш <> - вверх, <> - вниз, <> - вправо, <> - влево он определяет положение комнаты или двери. На экране постоянно присутствует меню подсказки, которое помогает пользователю ориентироваться. В нём указывается клавиши, с помощью которых пользователь может задать лабиринт. Например, при помощи клавиши <к> происходит ввод комнаты, при этом комната отображается в виде точки зелёного цвета, при помощи клавиши <д> происходит ввод двери, которая не рисуется а просто соединяет комнаты и представляет собой две перекрещивающиеся линии, т.е. можно соединять сразу несколько дверей в комнатах и рисовать лабиринт в трёх или в четырёх направлениях. При помощи клавиши <я> можно редактировать лабиринт т. е. удалять вершины или рёбра.

После ввода лабиринта в левом верхнем углу экрана выдаётся приглашение: “Введите вход в лабиринт ” после чего ожидается выбор одной из комнат в лабиринте, с помощью клавиш управления курсром и клавиши <Enter>, при этом выдаётся пиглашение: “Введите выход из лабиринта”. После выбора выхода программа выдаёт сообщение: “Кратчайший путь найден ” - в том случае, если он найден или “пути нет ” - если пути не существует. Если кратчайший путь найден, то он будет показан на графе в виде подсветки красным цветом. Далее предлагается выйти из программы путём нажатия клавиши <Esc> или начать ввод нового лабиринта нажав при этом любую клавишу. При этом существует клавиша <c> и <з> соответственно для сохранения лабиринта или загрузки уже существующего.

3 Технический проект

3.1 Диаграмма потоков данных

Программа имеет 4 основных процесса, отражающие основные функции программы:

Рисунок 3.1 – Диаграмма 1-го уровня

Рисунок 3.2 – Детализация процесса “Ввод лабиринта и его редактирование”

3.2 Словарь данных

Лабиринт – множество комнат, соединённых между собой дверьми.

Комната – символически изображенный квадрат, заданный в лабиринте.

Дверь –устройство, соединяющее комнаты.

Команда – в процессе диалоговой работы пользователя с программой, нажатие пользователем функциональной клавиши, за которой закреплено определенное действие. Существует 5 видов: ввод комнаты, ввод двери, удаление (комнаты или двери), сохранение и выход.

Команда ввод комнаты – нажатие пользователем клавиши <к>.

Команда ввод двери - нажатие пользователем клавиши <д>.

Команда удаление - нажатие пользователем клавиши <я>.

Команда сохранение - нажатие пользователем клавиши <с>.

Команда выход - нажатие пользователем клавиши <esc>.

Координаты – численное значение, определяющее положение объекта в лабиринте.

Карта поля – двумерный массив, который содержит координаты всех комнат и дверей.

Карта прохождения - двумерный массив, который содержит координаты комнат и дверей, через которые проходит кратчайший путь.

3.3 Спецификация процессов

Процесс 1 Ввод лабиринта и его редактирование.

Данный процесс служит для формирования лабиринта и его редактирования

Вход: координаты комнат и дверей

Выход: лабиринт

Действия: Формирование лабиринта путем заполнения его структуры координатами комнат и дверей.

Процесс 1.1 Ввод комнаты

Прежде чем передать процессу 1 координаты комнат или дверей, необходимо преобразовать команды пользователя по расстановке комнат и дверей, в соответствующие координаты для каждой комнаты и двери. Процессы 1.1-1.3 считывают код клавиши, нажатой пользователем, и в соответствии с кодом клавиши и местоположением курсора формируют код и координаты.

Вход: ввод комнаты

Выход: код и координаты комнаты

Процесс 1.2 Ввод двери

Вход: ввод двери

выход:код и координаты двери

Процесс 1.3 Удаление комнаты или двери

Процесс удаления записывает в структуру лабиринта код 0, по заданным координатам, что обозначает пустое место, т.е. комната или дверь была удалена из лабиринта.

Вход:удаление

Выход:код и координаты

Процесс 2 Поиск пути

Процесс поиск пути получает структуру лабиринта, и в соответствии с ней ищет возможные пути прохождения лабиринта, и путем сравнения выбирает самый короткий.

Вход: структура лабиринта

Выход: кратчайший путь в лабиринте.

Процесс 4 Отображение лабиринта

При вводе комнат или дверей необходимо чтобы пользователь видел отображение введенной информации на экране монитора. Данный процесс должен визуализировать лабиринт и найденный путь на экране.

Вход: координаты комнат и дверей

Выход: изображение лабиринта

Процесс 3 Сохранение введенных данных в файле

Для того чтобы координаты комнат или дверей не вводить заново при каждом запуске программы, необходимо сохранять их в файл.

Вход: структура лабиринта

Выход: файл с сохраненной структурой лабиринта

Процесс 3 Считывание данных из файла

Для того чтобы координаты комнат или дверей не вводить заново при каждом запуске программы, необходимо сохранять их в файл.

Вход: файл с сохраненной структурой лабиринта

Выход: структура лабиринта

3.4 Определение формы представления входных и выходных данных

Входные данные:

Это последовательность символов, вводимая пользователем с клавиатуры.

Выходные данные:

Отображение лабиринта и пути его прохождения на экране монитора, а также файл с сохраненным лабиринтом.

Команды:

загрузка лабиринта

сохранение лабиринта

создание комнаты

создание двери

удаление комнаты или двери

выход

3.5 Разработка структуры программы

Исходя из требований к программе, рациональней всего разделить ее на модули, взаимодействие которых показано на рисунке 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

Тестируемый модуль:

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 77 :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

Тестируемый модуль:

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

Текст программы

#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*R-R/2,SY+(y-1)*R+1,SX+x*R-R/2,SY+y*R-1);

line(SX+(x-1)*R+1,SY+y*R-R/2,SX+x*R-1,SY+y*R-R/2);

break;

case 'r' :P->Map[y][x]=2 ;

setcolor(UzelColor);setfillstyle(1,UzelColor);

fillellipse(SX+x*R-R/2,SY+y*R-R/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 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);

*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*R-R/2,SY+y*R-R/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*R-R/2,SY+y*R-R/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> в любой момент выполнения программы.