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


Лабораторная работа № 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;

}

Похожие статьи




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

Предыдущая | Следующая