Поиск кратчайшего пути в лабиринте на языке Си
Лабораторная работа № 3
Поиск кратчайшего пути в лабиринте на языке Си
Формулировка задания
Найти кратчайший путь в лабиринте от текущего положения до выхода.
Внешняя спецификация
Выходные данные: вывод исходного лабиринта, вывод лабиринта с указанными координатами текущего положения, вывод лабиринта с найденным кратчайшим путем. Варианты сообщений: "Найден кратчайший путь от A до B:", "В данном лабиринте невозможно пройти от точки A до B!".
Входные данные: координаты текущего положения и выхода из лабиринта (см. диалог) (вещественное число).
Главная функция: поиск кратчайшего пути (волновой алгоритм).
Диалог:
Введите координату X стартовой точки:
Введите координату Y стартовой точки:
Введите координату X финишной точки:
Введите координату Y финишной точки
Набор тестовых примеров (входные/выходные данные)
Тест №1: Найден кратчайший путь от точки A до B
Вход: X стартовой точки= 4, Y стартовой точки= 4, X финишной точки=6,
X финишной точки=6.
Выход: Печать "Найден кратчайший путь от A до B:"
Тест №2: В данном лабиринте невозможно пройти от точки A до B
Вход: X стартовой точки= 1, Y стартовой точки= 1, X финишной точки=4,
X финишной точки=4.
Выход: Печать "В данном лабиринте невозможно пройти от точки A до B:"
Структура данных
Имя |
Тип |
Описание |
Arr_size |
Вещественное число [-32000.00, 32000.00] |
Размер массива |
Labirint |
Двумерный массив вещественных чисел [arr_size] [arr_size] |
Массив, содержащий лабиринт |
St_x, St_y, En_x, En_y, |
Вещественное число [-32000.00, 32000.00] |
Координаты точек старта и финиша |
Функция void print_labirint()
Лабиринт путь алгоритм
Функция выводит на экран элементы лабиринта
Выходные данные: вывод лабиринта на экран с элементами соответствующими элементам массива(стена-"#",свободный путь-" ",стартовый элемент-"A", финишный элемент-"B", найденный путь-"O"),вывод шкалы координат по X, вывод шкалы координат по Y.
Входные данные: аргумент в виде массива вещественных чисел.
Набор тестовых примеров (входные/выходные данные)
Тест №1: Найдена стена
Вход: значение элемента массива = 1
Выход: Печать "#"
Тест №2: Найден свободный путь
Вход: значение элемента массива = 0
Выход: Печать " "
Тест №3: Найден стартовый элемент
Вход: значение элемента массива = -1
Выход: Печать "А"
Тест №4: Найден финишный элемент
Вход: значение элемента массива = -2
Выход: Печать "B"
Структура данных
Имя |
Тип |
Описание |
Arr |
Двумерный массив вещественных чисел [arr_size] [arr_size] |
Аргумент в виде двухмерного массива, передающий в функцию элементы лабиринта |
Функция bool LabirintFromFile(char*file)
Функция загружает элементы лабиринта из текстового файла в двухмерный массив, возвращает true, если загрузка прошла успешно, иначе сообщает об ошибке и возвращает false.
Файл содержит строки чисел 0 и 1,
Количество строк и чисел в одной строке соответствует размеру
Выделенного под массив (arr_size).
- 1-непроходимый участок, 0-проходимый участок.
Выходные данные: вывод элементов файла в виде 1 и 0 в двухмерный массив,
Вывод сообщения об ошибке. Варианты сообщений: "Ошибка! Невозможно открыть файл Labirint. txt для загрузки лабиринта!"
Входные данные: аргумент в виде строки, передающий в функцию имя текстового файла.
Структура данных
Имя |
Тип |
Описание |
File |
Массив символов Char* |
Аргумент в виде строки, передающий в функцию имя текстового файла |
Strm |
Указатель на открытый файловый поток FILE* |
Указатель на открытый файловый поток, Позволяет управлять файловым вводом/выводом |
Функция bool Find()
Функция поиска кратчайшего пути в двухмерном массиве, основанная на алгоритме волновой трассировки. Возвращает true в случае успешного поиска и выводит в массив, найденный кратчайший путь.
Выходные данные: вывод найденного кратчайшего пути в двухмерный массив.
Входные данные: двухмерный массив с указателями на проходимые и непроходимые участки.
Структура данных
Имя |
Тип |
Описание |
Add_front |
Булевая переменная [true, false] |
Индикатор прохождения фронта волны |
Temp_labirint |
Трехмерный массив веществен-ных чисел [arr_size] [arr_size] [3] |
Временный массив для хранения лабиринта и координат обратного пути |
X, y,i, j |
Вещественное число [-32000.00, 32000.00] |
Координаты массива |
Step |
Вещественное число [-32000.00, 32000.00] |
Счетчик фронта волны |
Start_x, start_y, end_x, end_y |
Вещественное число [-32000.00, 32000.00] |
Координаты точек A и B |
Start |
Булевая переменная [true, false] |
Индикатор стартовой позиции |
Temp_i, temp_j |
Вещественное число [-32000.00, 32000.00] |
Временная переменная для хранения координат фронта |
Алгоритм (в виде блок-схемы)
Найти кратчайший путь в лабиринте от текущего положения до выхода
Вход:--
Выход:
1. Загрузка лабиринта из текстового файла
Вход:file
Да нет
Выход: bool
1.1. Посимвольное чтение из файла и вывод в массив
Вход:--
Выход:--
2. Вывод лабиринта
Вход:arr
Выход:--
Проверка значений массива на соответствие значениям лабиринта
Вход:--
Выход:--
Поиск элемента "стена"
Вход:--
ДА НЕТ
Выход:--
Поиск стартовой позиции
Вход:--
ДА НЕТ
Выход:--
Поиск финишной позиции
Вход:--
ДА НЕТ
Выход:--
Поиск свободного пути
Вход:--
ДА НЕТ
Выход:--
Поиск элемента кратчайшего пути
Вход:--
ДА НЕТ
Выход:--
5. Поиск кратчайшего пути
Вход:labirint
Выход:temp_labirint
Заполнение временного массива указателями элементов лабиринта
Проверка значений массива на соответствие значениям лабиринта
Вход:--
Выход:--
Поиск элемента "стена"
Вход:--
ДА НЕТ
Выход:--
Поиск стартовой позиции
Вход:--
ДА НЕТ
Выход:--
Поиск финишной позиции
Вход:--
ДА НЕТ
Выход:--
Поиск свободного пути
Вход:--
ДА НЕТ
Выход:--
Волновой алгоритм поиска кратчайшего пути
Вход:--
нет
Да
Выход:--
Проверка соответствия позиции массива номеру фронта
Вход:--
Да нет
Выход:--
Проверка на проходимость участка по четырем направлениям
Вход:--
Выход:--
Проходимость вверх
Выход:--
да нет
Выход:--
Проходимость вниз
Выход:--
да нет
Выход:--
Проходимость влево
Выход:--
да нет
Выход:--
Проходимость вправо
Выход:--
да нет
Выход:--
Проверка на соответствие значения временного массива значению стартовой позиции
Вход:--
Да нет
Выход:--
Проверка выполнения условия прохождения всего массива
Вход:--
Да нет
Выход:--
Восстановление пройденного кратчайшего пути
Вход: temp_labirint
нет
да
да нет
Выход: labirint
Кодировка
#include "stdafx. h"
#include <windows. h>
#include <locale. h>
Const int arr_size=10;//размер массива
Void print_labirint(int arr[arr_size][arr_size]);//вывод лабиринта
Bool Find();//поиск кратчайшего пути
Bool LabirintFromFile(char*file);//загрузка лабиринта из файла
Int labirint[arr_size][arr_size];//массив для хранения лабиринта
/////////////////////////////////////////////////////////////////////
//загрузка лабиринта из файла
//функция возвращает true если загрузка прошла успешно
Bool LabirintFromFile(char*file)//параметр file указывает путь файла
{
/*текстовый файл содержит строки чисел (0 и 1),
Количество строк и чисел в одной строке соответствует размеру
Выделенного под массив (arr_size).
- 1-непроходимый участок, 0-проходимый участок.
*/
FILE *strm;//указатель на открытый файловый поток
Strm=fopen(file,"r");//открываем файл для чтения
If(strm==NULL)
{//если функция вернула NULL то указываем на ошибку открытия файла
Printf("%s%s%s","Ошибка! Невозможно открыть файл ",file," для загрузки лабиринта! ");
System("pause");
Return false;
}
For (int i=0;i<arr_size;i++)
{//проходим по массиву
For (int j=0;j<arr_size;j++)
{
Fscanf (strm,"%1d",&;labirint[i][j]);//посимвольно читаем из файла и пишем в массив
}
}
Fclose(strm);//закрываем файловый поток
Return true;//функция завершилась успешно
}
///////////////////////////////////////////////////////////////////////
//вывод лабиринта на экран
Void print_labirint(int arr[arr_size][arr_size])
{//вывод лабиринта на экран
For(int i=0;i<arr_size;i++)
{//проходим по всему массиву
Printf("%d",i);//вывод шкалы координат по X
For(int j=0;j<arr_size;j++)
{
If(arr[i][j]==1)
{//если стена то печатаем символ #
Printf("%s","#");
}
Else if(arr[i][j]==-1)
{//если стартовый элемент то печатаем символ A
Printf("%s","A");
}
Else if(arr[i][j]==-2)
{//если финишный элемент то печатаем символ B
Printf("%s","B");
}
Else if(arr[i][j]==0)
{//если свободный путь то печатаем символ пробел
Printf("%s"," ");
}
Else if(arr[i][j]==-3)
{//если найденный путь то печатаем символ O
Printf("%s","O");
}
}
Printf("%s"," ");
}
Printf("%s"," 0123456789 ");//вывод шкалы координат по Y
}
Bool Find()
{//функция поиска, возвращает true, если путь найден
Bool add_front=true;//индикатор прохождения фронта волны
Int temp_labirint[10][10][3];//временный массив для хранения лабиринта и координат обратного пути
Int x, y;//координаты массива
Int step=0;//счетчик фронта волны
Int start_x, start_y, end_x, end_y;//координаты точек A и B
////////////////////////////////////////////////////////////////
//заполнение временного массива указателями элементов лабиринта
For (x = 0; x < 10; x++)
{//проходим по всему массиву
For (y = 0; y < 10; y++)
{
If (labirint[x][y] == 1)
{//найдена стена
Temp_labirint[x][y][0] = -2;//указываем во временном массиве
}
Else if(labirint[x][y] == 0)
{//найден свободный участок
Temp_labirint[x][y][0] = -1;
}
Else if(labirint[x][y] == -1)
{//найдена стартовая позиция
Start_x=x;//присваиваем координаты позиции
Start_y=y;
Temp_labirint[x][y][0] = -1;
}
Else if(labirint[x][y] == -2)
{//найдена финишная позиция
End_x=x;
End_y=y;
Temp_labirint[x][y][0] = -1;
}
}
}
////////////////////////////////////////////////////////////////////
//алгоритм поиска кратчайшего пути в лабиринте, основанный на алгоритме волновой трассировки
Temp_labirint[end_x][end_y][0]=0;//ищем с финиша
While (add_front)//выполняем, пока есть непройденые участки и не найдена стартовая позиция
{
For (x = 0; x <10; x++)
{//идем по всему массиву
For (y = 0;y < 10; y++)
{
If (temp_labirint[x][y][0] == step)
{//если позиция массива равна номеру фронта проверяем в четырех направлениях
//приоритет направлений:влево, вверх, вправо, вниз
If (y - 1 >= 0 &;&; temp_labirint[x-1][y][0] != -2 &;&; temp_labirint[x-1][y][0] == -1)
{//влево, если участок не пройден и не является непроходимым
Temp_labirint[x-1][y][0] = step + 1;//записываем номер фронта
Temp_labirint[x-1][y][1]=x;//записываем координаты предыдущего фронта волны
Temp_labirint[x-1][y][2]=y;
}
If (x - 1 >= 0 &;&; temp_labirint[x][y-1][0] != -2 &;&; temp_labirint[x][y-1][0] == -1)
{
Temp_labirint[x][y-1][0] = step + 1;
Temp_labirint[x][y-1][1]=x;
Temp_labirint[x][y-1][2]=y;
}
If (y + 1 < 10 &;&; temp_labirint[x+1][y][0] != -2 &;&; temp_labirint[x+1][y][0] == -1)
{
Temp_labirint[x+1][y][0] = step + 1;
Temp_labirint[x+1][y][1] =x;
Temp_labirint[x+1][y][2] =y;
}
If (x + 1 < 10 &;&; temp_labirint[x][y+1][0] != -2 &;&; temp_labirint[x][y+1][0] == -1)
{
Temp_labirint[x][y+1][0] = step + 1;
Temp_labirint[x][y+1][1]=x;
Temp_labirint[x][y+1][2]=y;
}
}
}
}
Step++;//увеличиваем номер фронта волны
If (temp_labirint[start_x][start_y][0] != -1)//если дошли до старта
{
Add_front = false;//поиск окончен
}
If (step > arr_size * arr_size)//если прошли весь массив
{
Add_front = false;//поиск окончен
Return false;//невозможно найти выход
}
}
//////////////////////////////////////////////////////////////////////////////////////
//восcтанавливаем пройденный путь
Int i=start_x;//начинаем от старта
Int j=start_y;
Int temp_i;//временная переменная для хранения координат фронта
Int temp_j;
Bool start=true;//стартовая позиция
While(temp_labirint[i][j][0]!=0)
{//выполняем пока не дойдем до конца
If(!start)
{//если не стартовая позиция
Labirint[i][j]=-3;//отмечаем путь в лабиринте
}
Temp_i = temp_labirint[i][j][1];//извлекаем координаты следующего фронта
Temp_j = temp_labirint[i][j][2];
I=temp_i;//переходим к следующему фронту
J=temp_j;
Start=0;//стартовая позиция пройдена
}
Return true;//поиск успешно завершен
}
Int _tmain(int argc, _TCHAR* argv[])
{
//координаты стартовой точки
Int st_x;
Int st_y;
//координаты финишной точки
Int en_x;
Int en_y;
Setlocale(0,"rus");
////////////////////////////////////////////
//Загрузка лабиринта из текстового файла
If(!LabirintFromFile("Labirint. txt"))
{//если ошибка завершаем программу
return 0;
}
////////////////////////////////////////////
//вывод лабиринта
Print_labirint(labirint);
////////////////////////////////////////////
//ввод координат стартовой и финишной точек
Printf("%s","Введите координату X стартовой точки:");
Scanf("%d",&;st_x);
System("cls");//очистка экрана
Print_labirint(labirint);//вывод лабиринта
Printf("%s","Введите координату Y стартовой точки:");
Scanf("%d",&;st_y);
System("cls");
Labirint[st_y][st_x]=-1;//указываем стартовую точку
Print_labirint(labirint);
Printf("%s","Введите координату X финишной точки:");
Scanf("%d",&;en_x);
System("cls");
Print_labirint(labirint);
Printf("%s","Введите координату Y финишной точки:");
Scanf("%d",&;en_y);
System("cls");
Labirint[en_y][en_x]=-2;//указываем финишную точку
Print_labirint(labirint);
/////////////////////////////////////////////
//поиск кратчайшего пути
If(Find())
{//если поиск удачен
Printf("%s","Найден кратчайший путь от A до B: ");
Print_labirint(labirint);//вывод лабиринта с отмеченным путем
}
Else
{//иначе, сообщаем о неудаче
Printf("%s","В данном лабиринте невозможно пройти от точки A до B!");
}
Printf("%s"," ");
System("pause");
Return 0;
}
Похожие статьи
-
ДВОИЧНЫЙ ПОИСК, АВЛ-Дерево - Структуры и алгоритмы обработки данных
Алгоритм двоичного поиска в упорядоченном массиве сводится к следующему. Берем средний элемент отсортированного массива и сравниваем с ключом X. Возможны...
-
CoDeSys -- универсальный инструмент разработки прикладных программ для программируемых логических контроллеров на языках стандарта IEC 61131-3. Данный...
-
Если в результате поиска на схеме по данным из таблицы будет найдено несколько экземпляров оборудования (т. е. с одинаковой маркировкой или...
-
Для того, чтобы строить диаграммы в соответствии с рисунком 2.7, необходимо реализовать алгоритм соединения двух объектов линией. Для отображения линии...
-
Подпрограммы - Язык программирования PERL. Сфера применения
Как и все структурированные языки программирования, Perl поддерживает подпрограммы. Подпрограмма может быть определена с помощью ключевого слова sub, как...
-
ОПЕРАТОР ВВОДА ДЛЯ ЧТЕНИЯ ФАЙЛА, ОПЕРАТОР ВЫВОДА - Язык программирования Паскаль
Оператор ввода для чтения файла обладает всеми свойствамии обычного оператора READ. Вкачестве параметров могут быть переменные; каждая переменная поучает...
-
Исходя из данных первого пункта выяснили, что используется web сервер "Nginx". Данный сервер работает на Unix-подобных операционных системах. Никакая из...
-
При извлечении текста из Интернета, он не имеет никой разметки и представлен в виде сплошного набора предложений. Для дальнейшего использования...
-
Поиск приятелей и коллег - Microsoft Internet Explorer 3.0
Средство Finger позволяет проверить правильность адреса электронной почты, полученный от приятеля или коллеги. Вы вводите почтовый адрес человека, и...
-
Информационные ресурсы сети Интернет - Поиск информации в сети Интернет
Благодаря повсеместному развитию и применению компьютерных технологий в настоящее время в той или иной электронной форме находится информация всех...
-
Поиск и замена текста При работе с длинными документами иногда приходится вносить в них повторяющиеся изменения. ПрограммаWriterимеет специальные...
-
С помощью диалоговых окон были отображены задания, их выбор, поля для ввода входных данных, заполняемые по умолчанию, полученный результат и визуализация...
-
Интерфейс пользователя - Система поиска автобусных маршрутов
Интерфейс программы показан на рисунке 2.1. Рисунок 2.1 -- Интерфейс пользователя Программа выполнена с использованием MDI-интерфейса. Интерфейс содержит...
-
Исходные данные, Пользовательские типы данных - Система поиска автобусных маршрутов
Пользовательские типы данных В программе использовано несколько пользовательских типов данных. Так как программа написана с использованием...
-
Характеристики ЛВС Используемый стандарт: IEEE 802.3ab -- стандарт, использующий витую пару категорий 5e. 1000BASE-T, стандарт Gigabit Ethernet....
-
Скалярные переменные - Язык программирования PERL. Сфера применения
Как отмечалось, скалярная переменная может содержать единственное значение. В языке Perl имена скалярных переменных всегда начинаются со знака ($). В еле...
-
Линии и точки, Многоугольники - Работа с языком Турбо Паскаль
Процедура PutPixel. Выводит заданным цветом точку по указанным координатам. Заголовок: Procedure PutPixel(X, Y: Inteder; Color: word); Здесь X, Y -...
-
ФУНКЦИИ И ПРОЦЕДУРЫ, Модуль Graph, Координаты, окна, страницы - Работа с языком Турбо Паскаль
Модуль Graph Модуль Graph Турбо Паскаля содержит около пятидесяти различных процедур и функции, предназначенных для работы с графическим экраном. В этом...
-
В настоящее время существует большое количество поисковых систем, но большинство из них основано на методе, в соответствии с которым документы...
-
Синтаксис объявления класса в языке С++ имеет следующий вид: Class<имя класса>: <спецификатор доступа><имя базового класса> { Элементы класса...
-
Для вызова ЛЕКСИКОНа следует набрать LEXICON или LEXICON имя редактируемого - файла Если в команде вызова ЛЕКСИКОНа указано имя файла, которого нет на...
-
Паттерн репозиторий - Программирование на языке C++
Паттерн Repository Посредничает между уровнями области определения и распределения данных (domain and data mapping layers), используя интерфейс, схожий с...
-
МОДУЛИ - Язык программирования Паскаль
Наличие модулей в Turbo Pascal позволяет программировать и отлаживать программу по частям, создавать библиотеки подпрограмм и данных, воспользоваться...
-
Алгоритмы распознавания интервальных и единичных интервальных графов [2,5-7] основываются на специальном упорядочивании вершин графа и проверке...
-
ПРОЦЕДУРЫ - Язык программирования Паскаль
Delete (St, Pos, N) - удаление N символов строки St, начиная с позиции Pos. Если значение Pos > 255, возникает ошибка. Значение St Выражение Результат...
-
Язык разметки XML - Компьютерная лингвистика в образовательной среде
XML - это расширяемый язык разметки (ExtensibleMarkupLanguage). Был разработан в соответствии с основными требованиями сервера WWW. Является достаточно...
-
Проектирование и разработка сайта Средства разработки Язык гипертекстовой разметки HTML В Интернете сосредотачивается и передается достаточно большое...
-
Поиск, сбор и хранение научной информации - Поиск, накопление и обработка информации
Не все окружающие нас источники информации можно использовать для подготовки научных работ. Ведь научная работа всегда имеет достаточно узкую...
-
Поиск максимума функции F(x) на отрезке [a;b] - Вычисление максимума функции с некоторыми критериями
Постановка задачи: Необходимо численным методом найти максимум функции F(x)=-L(x1)x2+3.1L(x2)x+5 На отрезке [a;b] с точностью е, при том, что L(x1) и...
-
1. НА 7 ПК ИСПОЛЬЗУЕТСЯ microsoft Windows xp sp2. 2. на 1 используется Altlinux 5 3. Программы офисного назначения: A) Microsoft Office Excel 2003 B)...
-
Вычислить максимум функции F(x)=-L(x1)x2+3.1L(x2)x+5 на отрезке [a;b] с точностью е. L(x1), L(x2) - значения интерполяционного многочлена, построенного...
-
Введение - Поиск, накопление и обработка информации
Умственный труд в любой его форме всегда связан с поиском информации. Тот факт, что этот поиск становится сейчас все сложнее и сложнее, в доказательствах...
-
Основные требования к поиску - Поиск информации в сети Интернет
Поисковый система файл яндекс К результатам поиска предъявляются требования полноты охвата ресурсов, достоверности полученной информации, минимальных...
-
Поисковые каталоги, Поисковые индексы - Поиск информации в сети Интернет
Поисковые каталоги служат для тематического поиска. Информация на этих серверах структурирована по темам и подтемам. Имея намерение осветить какую-то...
-
Поиск информации, Средства поиска файлов. - Поиск информации в сети Интернет
Средства поиска файлов. Поиск файла вручную в сложной структуре каталогов ftp-сервера может занять достаточно много времени. Для упрощения и ускорения...
-
Введение - Поиск информации в сети Интернет
Сеть Интернет похожа на огромную мировую библиотеку, имеющую только одно, но существенное отличие: для поиска книги в библиотеке есть каталог, в крайнем...
-
Постановка задачи Необходимо разработать программу для поиска автобусных маршрутов. В качестве среды разработки должна использоваться Delphi 7. В...
-
В Internet есть компьютеры которые позволяют вашему компьютеру действовать как терминал. Этот процесс называется удаленным входом (Telnetting). Tермин...
-
Первый способ нахождения обесцененной лексики в текстах является самым простым. Данный способ - это простой поиск по совпадению, то есть мы берем слово...
-
Сформулируем задачу поиска оптимального регулятора в общих понятиях: дан многомерный реальный объект управления с квадратной матричной передаточной...
Поиск кратчайшего пути в лабиринте на языке Си