Поиск в лабиринте

Курсовая работа по программированию

"Поиск в лабиринте"

Поиск в глубину:

Алгоритм

Реализация алгоритма поиска:

Поиск в лабиринте реализован поиском в глубину (рекурсивно)

Данная реализация представлена в программе классом 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;

}

}

}

// Возвращаем число доступных позиций.

returncount;

}

Поиск в лабиринте.

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;

}

/**/

//Красим вешину в серый цвет, т.е. начали её обработку

color[y][x]=1;

delay(500);

count_p++;

path[count_p].x=x;

path[count_p].y=y;

setcolor(BLUE);

//defaultmouseoff;

gui->Circle(sx+x*edge-edge / 2, sy+y*edge-edge / 2, 3);

//defaultmouseon;