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

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

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

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

Алгоритм

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

Поиск в лабиринте реализован поиском в глубину (рекурсивно) Данная реализация представлена в программе классом tLabirint.

Условно реализацию данного алгоритма можно разбить на несколько составляющих:

Считывание матрицы лабиринта из файла Нахождение доступных (смежных) позиций в лабиринте (тех мест, куда можно ходить) для каждой позиции на каждой итерации поиска.

Поиск с пошаговым выводом результатов.

Считывание матрицы лабиринта из файла.

Матрица лабиринта хранится в виде матрицы, а размерностью 51Х51. 51Х51 на мой взгляд достаточно.

Формат входного файла:

1 стока: размерность матрицы лабиринта

2 строка: координата Х начальной (стартовой) позиции

3 строка: координата Y начальной (стартовой) позиции

4 строка: координата Х конечной (финальной) позиции

5 строка: координата Y конечной (финальной) позиции Затем идет матрица лабиринта размерность n символов на n строк, где n — число из первой строки файла, размерность матрицы Причем символ «1» означает доступность клетки символ «0» означает препятствие Пример входного файла:

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;

}

/**/

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

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;

//printf («X-%d;Y-%dn», x, y);

//getchar ();

if ((finish.x==x) && (finish.y==y))

flag=1;

/**/

// Получаем координаты лабиринта, куда можно идти

cnt=GetCommon (y, x, sm);

for (i=1;i<=cnt;i++)

{

// Если позиция в лабиринте белого цвета, т. е. ещё ни разу не подвергалась обработке и если не достигнута финальная позиция

if (color[sm[i]. y][sm[i].x]==0 && flag==0)

// Просматриваем эти координаты

DFS_Visit (sm[i]. y, sm[i]. x);

}

color[y][x]=2; // Красим позицию в черный цвет, т. е. все возможные варианты у данной позиции рассмотрены.

}

Графический вывод

В программе реализована иерархия классов для работы в графическом режиме и вывода необходимого на экран.

Базовый класс.

У него имеются только координаты.

class tMyObj

{

protected:

int x0, y0;

public:

tMyObj (){};

~tMyObj (){};

tMyObj (int _x, int _y){x0=_x;y0=_y;};

};

Класс линия

Это производный класс, он имеет к тому же две пары координат (начальная и конечная точки).

class tMyLine: public tMyObj

{

int x1, y1;

public:

tMyLine (){};

~tMyLine (){};

tMyLine (int _x, int _y, int _x1, int _y1):tMyObj (_x, _y){x1=_x1;y1=_y1;};

void Show (){line (x0, y0, x1, y1);};

void Hide (){int o = getcolor ();int b = getbkcolor ();setcolor (b);Show ();setcolor (o);}

};

Класс окружность.

Это производный от базового класса tMyObj класс. Он имеет кроме координат радуис.

class tMyCircle: public tMyObj

{

int rad;

public:

tMyCircle (){};

~tMyCircle (){};

tMyCircle (int _x, int _y, int _rad):tMyObj (_x, _y){rad=_rad;};

void Show (){circle (x0, y0, rad);}

};

Класс прямоугольник.

Это производный от базового класса tMyObj класс имеет две пары координат (Левую верхнюю и правую нижнюю точки)

class tMyRect: public tMyObj

{

int x1, y1;

public:

tMyRect (){};

~tMyRect (){};

tMyRect (int _x, int _y, int _x1, int _y1):tMyObj (_x, _y){x1=_x1;y1=_y1;};

void Show (){rectangle (x0, y0, x1, y1);};

void Hide (){int o = getcolor ();int b = getbkcolor ();setcolor (b);Show ();setcolor (o);}

};

Класс графических примитивов.

Класс графических примитивов позволяет выводить графические объекты: линия, окружность, прямоугольник, на экран. Это достигается созданием объектов классов примитивов, т. е. объектов классов линия, окружность, прямоугольник.

class tMyGUI

{

public:

tMyGUI ();

~tMyGUI ();

void Line (int x, int y, int x1, int y1);

void Circle (int x, int y, int rad);

void Rectangle (int x, int y, int x1, int y1);

void Fill (int x, int y, int Color);

};

void tMyGUI: Line (int x, int y, int x1, int y1)

{

tMyLine tl (x, y, x1, y1);

tl.Show ();

}

void tMyGUI: Circle (int x, int y, int rad)

{

tMyCircle tc (x, y, rad);

tc.Show ();

}

void tMyGUI: Rectangle (int x, int y, int x1, int y1)

{

tMyRect tr (x, y, x1, y1);

tr.Show ();

}

void tMyGUI: Fill (int x, int y, int Color)

{

floodfill (x, y, Color);

}

tMyGUI:tMyGUI ()

{

int gdriver = DETECT, gmode, errorcode;

initgraph (&gdriver, &gmode, «»);

errorcode = graphresult ();

if (errorcode ≠ grOk) /* an error occurred */

{

printf («Graphics error: %sn», grapherrormsg (errorcode));

printf («Press any key to halt:»);

getch ();

exit (1);

/* return with error code */

}

}

tMyGUI:~tMyGUI ()

{

closegraph ();

}

Дополнительные типы данных, используемые в программе

Тип координат.

Представляет собой структуру с двумя полями x и y.

typedef struct _tCoords

{

int x;

int y;

} tCoords;

Тип Смежность

Объявлен как массив на 51 элемент типа tCoords

typedef tCoords smezh[51];

Константы.

Максимальная длина пути.

const MAX_PATH=100;

Исходный текст программы:

#include

#include

#include

#include

#include

#include

typedef struct _tCoords

{

int x;

int y;

} tCoords;

typedef tCoords smezh[51];

const MAX_PATH=100;

class tMyObj

{

protected:

int x0, y0;

public:

tMyObj (){};

~tMyObj (){};

tMyObj (int _x, int _y){x0=_x;y0=_y;};

};

class tMyLine: public tMyObj

{

int x1, y1;

public:

tMyLine (){};

~tMyLine (){};

tMyLine (int _x, int _y, int _x1, int _y1):tMyObj (_x, _y){x1=_x1;y1=_y1;};

void Show (){line (x0, y0, x1, y1);};

void Hide (){int o = getcolor ();int b = getbkcolor ();setcolor (b);Show ();setcolor (o);}

};

class tMyCircle: public tMyObj

{

int rad;

public:

tMyCircle (){};

~tMyCircle (){};

tMyCircle (int _x, int _y, int _rad):tMyObj (_x, _y){rad=_rad;};

void Show (){circle (x0, y0, rad);}

};

class tMyRect: public tMyObj

{

int x1, y1;

public:

tMyRect (){};

~tMyRect (){};

tMyRect (int _x, int _y, int _x1, int _y1):tMyObj (_x, _y){x1=_x1;y1=_y1;};

void Show (){rectangle (x0, y0, x1, y1);};

void Hide (){int o = getcolor ();int b = getbkcolor ();setcolor (b);Show ();setcolor (o);}

};

class tMyGUI

{

public:

tMyGUI ();

~tMyGUI ();

void Line (int x, int y, int x1, int y1);

void Circle (int x, int y, int rad);

void Rectangle (int x, int y, int x1, int y1);

void Fill (int x, int y, int Color);

};

void tMyGUI: Line (int x, int y, int x1, int y1)

{

tMyLine tl (x, y, x1, y1);

tl.Show ();

}

void tMyGUI: Circle (int x, int y, int rad)

{

tMyCircle tc (x, y, rad);

tc.Show ();

}

void tMyGUI: Rectangle (int x, int y, int x1, int y1)

{

tMyRect tr (x, y, x1, y1);

tr.Show ();

}

void tMyGUI: Fill (int x, int y, int Color)

{

floodfill (x, y, Color);

}

tMyGUI:tMyGUI ()

{

int gdriver = DETECT, gmode, errorcode;

initgraph (&gdriver, &gmode, «»);

errorcode = graphresult ();

if (errorcode ≠ grOk) /* an error occurred */

{

printf («Graphics error: %sn», grapherrormsg (errorcode));

printf («Press any key to halt:»);

getch ();

exit (1);

/* return with error code */

}

}

tMyGUI:~tMyGUI ()

{

closegraph ();

}

class tLabirint

{

int a[51][51];

// Матрица лабиринта

tCoords path[MAX_PATH+1]; // Путь

int color[51][51];

// Массив цветов. Используется в поиске для помечивания позиций в лабиринте

int count_a; // Размерность матрицы лабиринта

int count_p; // Длинна пути. т. е. кол-во элементов в массиве path

int flag; // Эта переменная показывает достигнута конечная позиция или нет

tCoords start, finish; // Координаты позиций начальной и конечной

int cx, cy; // Центр экрана

int edge; // Размер ребра

int sx, sy; // Начальные координаты для рисования лабиринта

int fx, fy; // Конечные координаты для рисования лабиринта

tMyGUI *gui; // Объект класса вывода графических примитивов

public:

tLabirint (); // конструктор

~tLabirint (); // Деструктор

void ReadMatrix (); // Считать матрицу

int GetCommon (int i, int j, smezh &s); // Найти доступную позицию в лабиринте

void DFS_Visit (int y, int x); // Просмотреть позицию в лабиринте

void DFS (); // Поиск в глубь

void DrawLabirint (); // Нарисовать лабиринт

void GetCoords (); // Считать координаты начальной и конечной позиции

void Find (); // Искать путь

};

tLabirint:tLabirint ()

{

int i, j;

flag=0;

start.x=0;

start.y=0;

finish.x=0;

finish.y=0;

for (i=1;i<=count_a;i++)

for (j=1;j<=count_a;j++)

color[i][j]=0;

for (i=1;i<=MAX_PATH;i++)

{

path[i]. x=0;

path[i].y=0;

}

count_p=0;

gui = new tMyGUI ();

}

tLabirint:~tLabirint ()

{

delete gui;

}

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);

//Chitat' startovuyu pozitciu: X

fread (&ch, sizeof (ch), 1, f);

start.x = atoi (&ch);

fread (&ch, sizeof (ch), 1, f);

//Chitat' startovuyu pozitciu: Y

fread (&ch, sizeof (ch), 1, f);

start.y = atoi (&ch);

fread (&ch, sizeof (ch), 1, f);

//Chitat' final’nuyu pozitciu: X

fread (&ch, sizeof (ch), 1, f);

finish.x = atoi (&ch);

fread (&ch, sizeof (ch), 1, f);

//Chitat' final’nuyu pozitciu: Y

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»);

}

*/

}

int tLabirint: GetCommon (int i, int j, smezh &s)

{

//struct

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)

{

count++;

s[count].x=check[k].x;

s[count].y=check[k].y;

}

}

}

return count;

}

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;

//printf («X-%d;Y-%dn», x, y);

//getchar ();

if ((finish.x==x) && (finish.y==y))

flag=1;

/**/

cnt=GetCommon (y, x, sm);

for (i=1;i<=cnt;i++)

{

if (color[sm[i]. y][sm[i].x]==0 && flag==0)

DFS_Visit (sm[i]. y, sm[i]. x);

}

color[y][x]=2;

}

void tLabirint: DFS ()

{

flag=0;

DFS_Visit (start.y, start. x);

}

void tLabirint: DrawLabirint ()

{

int i, j;

edge=15;

cx=getmaxx () / 2;

cy=getmaxy () / 2;

sx=cx-((count_a / 2)*edge-(edge / 2));

sy=cy-((count_a / 2)*edge-(edge / 2));

fx=sx+count_a*edge;

fy=sy+count_a*edge;

setcolor (RED);

gui->Rectangle (sx, sy, fx, fy);

for (i=1;i<=count_a;i++)

gui->Line (sx+i*edge, sy, sx+i*edge, fy);

for (i=1;i<=count_a;i++)

gui->Line (sx, sy+i*edge, fx, sy+i*edge);

for (i=1;i<=count_a;i++)

{

for (j=1;j<=count_a;j++)

{

if (a[i][j]==1)

gui->Fill (sx+(j*edge)-edge / 2, sy+(i*edge)-edge / 2, RED);

}

}

}

void tLabirint: GetCoords ()

{

/*

start.x=1;

start.y=1;

finish.x=5;

finish.y=4;

*/

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);

//Chitat' startovuyu pozitciu: X

fread (&ch, sizeof (ch), 1, f);

start.x = atoi (&ch);

fread (&ch, sizeof (ch), 1, f);

//Chitat' startovuyu pozitciu: Y

fread (&ch, sizeof (ch), 1, f);

start.y = atoi (&ch);

fread (&ch, sizeof (ch), 1, f);

//Chitat' final’nuyu pozitciu: X

fread (&ch, sizeof (ch), 1, f);

finish.x = atoi (&ch);

fread (&ch, sizeof (ch), 1, f);

//Chitat' final’nuyu pozitciu: Y

fread (&ch, sizeof (ch), 1, f);

finish.y = atoi (&ch);

fread (&ch, sizeof (ch), 1, f);

}

void tLabirint: Find ()

{

GetCoords ();

DFS ();

if (flag==0)

outtextxy (20, 440, «No way!»);

else

outtextxy (20, 440, «Found way!»);

}

void main ()

{

tLabirint *lab;

clrscr ();

lab = new tLabirint ();

lab->ReadMatrix ();

lab->DrawLabirint ();

lab->Find ();

/**/

getch ();

delete lab;

}