Курсовая работа по программированию
"Поиск в лабиринте"
Поиск в глубину:
Алгоритм
Реализация алгоритма поиска:
Поиск в лабиринте реализован поиском в глубину (рекурсивно)
Данная реализация представлена в программе классом tLabirint.
Условно реализацию данного алгоритма можно разбить на несколько составляющих:
· Считывание матрицы лабиринта из файла
· Нахождение доступных (смежных) позиций в лабиринте (тех мест, куда можно ходить) для каждой позиции на каждой итерации поиска.
· Поиск с пошаговым выводом результатов.
Считывание матрицы лабиринта из файла.
Матрица лабиринта хранится в виде матрицы а размерностью 51Х51. 51Х51 на мой взгляд достаточно.
Формат входного файла:
1 стока: размерность матрицы лабиринта
2 строка: координата Х начальной (стартовой) позиции
3 строка: координата Y начальной (стартовой) позиции
4 строка: координата Х конечной (финальной) позиции
5 строка: координата Y конечной (финальной) позиции
Затем идет матрица лабиринта размерность n символов на n строк, где n — число из первой строки файла, размерность матрицы
Причем символ «1» означает доступность клетки
символ «0» означает препятствие
Пример входного файла:
5
1
1
5
4
11010
01110
11100
00111
10000
void tLabirint::ReadMatrix()
{
FILE *f;
char ch;
int i,j,n;
//Открываем файл
f = fopen("input.txt", "rt");
// Считываем размерность
fread(&ch,sizeof(ch), 1, f);
// Переводим в число
n = atoi(&ch);
// Считываем перевод строки
fread(&ch, sizeof(ch), 1, f);
// Читаем стартовую позицию Х
fread(&ch,sizeof(ch), 1, f);
start.x = atoi(&ch);
// Считываем перевод строки
fread(&ch, sizeof(ch), 1, f);
//Читаем стартовую позицию У
fread(&ch,sizeof(ch), 1, f);
start.y = atoi(&ch);
// Считываем перевод строки
fread(&ch, sizeof(ch), 1, f);
//Читаем финальную позицию Х
fread(&ch,sizeof(ch), 1, f);
finish.x = atoi(&ch);
// Считываем перевод строки
fread(&ch, sizeof(ch), 1, f);
// Читаем финальную позицию У
fread(&ch,sizeof(ch), 1, f);
finish.y = atoi(&ch);
// Считываем перевод строки
fread(&ch, sizeof(ch), 1, f);
count_a=n;
memset(a, 0, sizeof(a));
// Считываем матрицу лабиринта
for(i=1;i<=count_a;i++)
{
for(j=1;j<=count_a;j++)
{
fread(&ch, sizeof(ch), 1, f);
a[i][j]=atoi(&ch);
ch=0;
}
// Считываем перевод строки
fread(&ch, sizeof(ch), 1, f);
}
fclose(f);
/*
for(i=1;i<=count_a;i++)
{
for(j=1;j<=count_a;j++)
printf("%d", a[i][j]);
printf("\n");
}
*/
}
Нахождение свободных мест в лабиринте.
Функция берет в качестве параметров текущие координаты i, j, соответственно X и Y. Ссылку на массив координат s
int tLabirint::GetCommon(int i, int j, smezh &s)
{
tCoords check[5];
int k, count;
count=0;
// Вверх
check[1].x=j;
check[1].y=i-1;
// В право
check[2].x=j+1;
check[2].y=i;
// Вниз
check[3].x=j;
check[3].y=i+1;
// Влево
check[4].x=j-1;
check[4].y=i;
for(k=1;k<=4;k++)
{
// Если не достигнуты границы матрицы,
if((check[k].x>0) && (check[k].y>0) && (check[k].x<=count_a) && (check[k].y<=count_a))
{
// То проверяем на доступность
if(a[check[k].y][check[k].x]==1)
{
// И если позиция с координатами X, Y доступна, то добавляем к эту позицию в массив s доступных позиций
count++; s[count].x=check[k].x;
s[count].y=check[k].y;
}
}
}
// Возвращаем число доступных позиций.
return count;
}
Поиск в лабиринте.
void tLabirint::Find()
{
GetCoords(); // Получить начальные и конечные координаты
DFS();//произвести поиск
if(flag==0)
outtextxy(20, 440, "No way!"); //Если путь не найден
else
outtextxy(20, 440, "Found way!"); //Если найден путь
}
void tLabirint::DFS()
{
flag=0; // Изначально нет пути
DFS_Visit(start.y, start.x); // начинаем поиск
}
void tLabirint::DFS_Visit(int y, int x)
{
int i;
int cnt;
smezh sm;
// Искомая вершина достигнута?
if(flag==1)
{
// Если да, то выход
exit;
}
/**/
//Красим вешину в серый цвет, т.е. ............
