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

Размещено на http://www.allbest.ru/

Лабораторная работа № 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," для загрузки лабиринта!\n");

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","\n");

}

printf("%s"," 0123456789\n");//вывод шкалы координат по 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:\n");

print_labirint(labirint);//вывод лабиринта с отмеченным путем

}

else

{//иначе,сообщаем о неудаче

printf("%s","В данном лабиринте невозможно пройти от точки A до B!");

}

printf("%s","\n");

system("pause");

return 0;

}

Размещено на Allbest.ru