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

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

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

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

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

Алгоритм

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

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

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

}

/**/

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

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-%d\n", 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: %s\n", 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 <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <graphics.h>

#include <conio.h>

#include <dos.h>

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: %s\n", 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-%d\n", 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;

}