Курсоваяработа по программированию
«Поиск в лабиринте»
Поиск в глубину:
Алгоритм
/>
Реализация алгоритмапоиска:
Поиск в лабиринтереализован поиском в глубину (рекурсивно)
Данная реализацияпредставлена в программе классом 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
voidtLabirint::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
{
for(j=1;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
{
for(j=1;j
printf("%d",a[i][j]);
printf("\n");
}
*/
}
Нахождение свободныхмест в лабиринте.
Функция берет в качествепараметров текущие координаты i, j, соответственно X и Y. Ссылку на массивкоординат s
inttLabirint::GetCommon(int i, int j, smezh &s)
{
tCoordscheck[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
{
// Если не достигнутыграницы матрицы,
if((check[k].x>0)&& (check[k].y>0) && (check[k].x
{
// То проверяем надоступность
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;
}
Поисквлабиринте.
voidtLabirint::Find()
{
GetCoords(); // Получитьначальные и конечные координаты
DFS();//произвести поиск
if(flag==0)
outtextxy(20, 440,«No way!»); //Если путь не найден
else
outtextxy(20,440, «Found way!»); //Если найден путь
}
voidtLabirint::DFS()
{
flag=0; // Изначально нетпути
DFS_Visit(start.y, start.x); //начинаем поиск
}
voidtLabirint::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
{
// Если позиция влабиринте белого цвета, т.е. ещё ни разу не подвергалась обработке и если недостигнута финальная позиция
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;};
};
Класс линия
Это производный класс, онимеет к тому же две пары координат( начальная и конечная точки).
classtMyLine:public tMyObj
{
int x1, y1;
public:
tMyLine(){};
~tMyLine(){};
tMyLine(int_x, int _y, int _x1, int _y1):tMyObj(_x, _y){x1=_x1;y1=_y1;};
voidShow(){line(x0, y0, x1, y1);};
voidHide(){int o = getcolor();int b = getbkcolor();setcolor(b);Show();setcolor(o);}
};
Классокружность.
Это производный от базового класса tMyObj класс. Он имеет кроме координат радуис.
classtMyCircle:public tMyObj
{
int rad;
public:
tMyCircle(){};
~tMyCircle(){};
tMyCircle(int_x, int _y, int _rad):tMyObj(_x, _y){rad=_rad;};
voidShow(){circle(x0, y0, rad);}
};
Класс прямоугольник.
Это производный отбазового класса tMyObj класс имеет две пары координат (Левую верхнюю и правуюнижнюю точки)
classtMyRect:public tMyObj
{
int x1, y1;
public:
tMyRect(){};
~tMyRect(){};
tMyRect(int_x, int _y, int _x1, int _y1):tMyObj(_x, _y){x1=_x1;y1=_y1;};
voidShow(){rectangle(x0, y0, x1, y1);};
voidHide(){int o = getcolor();int b = getbkcolor();setcolor(b);Show();setcolor(o);}
};
Класс графическихпримитивов.
Класс графическихпримитивов позволяет выводить графические объекты: линия, окружность,прямоугольник, на экран. Это достигается созданием объектов классов примитивов,т.е. объектов классов линия, окружность, прямоугольник.
class tMyGUI
{
public:
tMyGUI();
~tMyGUI();
void Line(intx, int y, int x1, int y1);
voidCircle(int x, int y, int rad);
voidRectangle(int x, int y, int x1, int y1);
void Fill(intx, int y, int Color);
};
voidtMyGUI::Line(int x, int y, int x1, int y1)
{
tMyLine tl(x,y, x1, y1);
tl.Show();
}
voidtMyGUI::Circle(int x, int y, int rad)
{
tMyCircletc(x, y, rad);
tc.Show();
}
voidtMyGUI::Rectangle(int x, int y, int x1, int y1)
{
tMyRect tr(x,y, x1, y1);
tr.Show();
}
voidtMyGUI::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(«Graphicserror: %s\n», grapherrormsg(errorcode));
printf(«Pressany key to halt:»);
getch();
exit(1);
/* return witherror code */
}
}
tMyGUI::~tMyGUI()
{
closegraph();
}
Дополнительные типыданных, используемые в программе
Тип координат.
Представляет собойструктуру с двумя полями x и y.
typedef struct _tCoords
{
int x;
int y;
} tCoords;
Тип Смежность
Объявлен как массив на 51элемент типа tCoords
typedef tCoords smezh[51];
Константы.
Максимальная длина пути.
constMAX_PATH=100;
Исходный текстпрограммы:
#include
#include
#include
#include
#include
#include
typedef struct_tCoords
{
int x;
int y;
} tCoords;
typedeftCoords smezh[51];
constMAX_PATH=100;
class tMyObj
{
protected:
int x0, y0;
public:
tMyObj(){};
~tMyObj(){};
tMyObj(int _x,int _y){x0=_x;y0=_y;};
};
classtMyLine:public tMyObj
{
int x1, y1;
public:
tMyLine(){};
~tMyLine(){};
tMyLine(int_x, int _y, int _x1, int _y1):tMyObj(_x, _y){x1=_x1;y1=_y1;};
voidShow(){line(x0, y0, x1, y1);};
voidHide(){int o = getcolor();int b = getbkcolor();setcolor(b);Show();setcolor(o);}
};
classtMyCircle:public tMyObj
{
int rad;
public:
tMyCircle(){};
~tMyCircle(){};
tMyCircle(int_x, int _y, int _rad):tMyObj(_x, _y){rad=_rad;};
voidShow(){circle(x0, y0, rad);}
};
classtMyRect:public tMyObj
{
int x1, y1;
public:
tMyRect(){};
~tMyRect(){};
tMyRect(int_x, int _y, int _x1, int _y1):tMyObj(_x, _y){x1=_x1;y1=_y1;};
voidShow(){rectangle(x0, y0, x1, y1);};
voidHide(){int o = getcolor();int b = getbkcolor();setcolor(b);Show();setcolor(o);}
};
class tMyGUI
{
public:
tMyGUI();
~tMyGUI();
void Line(intx, int y, int x1, int y1);
voidCircle(int x, int y, int rad);
voidRectangle(int x, int y, int x1, int y1);
void Fill(intx, int y, int Color);
};
voidtMyGUI::Line(int x, int y, int x1, int y1)
{
tMyLine tl(x,y, x1, y1);
tl.Show();
}
voidtMyGUI::Circle(int x, int y, int rad)
{
tMyCircletc(x, y, rad);
tc.Show();
}
voidtMyGUI::Rectangle(int x, int y, int x1, int y1)
{
tMyRect tr(x,y, x1, y1);
tr.Show();
}
voidtMyGUI::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(«Graphicserror: %s\n», grapherrormsg(errorcode));
printf(«Pressany key to halt:»);
getch();
exit(1);
/* return witherror code */
}
}
tMyGUI::~tMyGUI()
{
closegraph();
}
classtLabirint
{
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
for(j=1;j
color[i][j]=0;
for(i=1;i
{
path[i].x=0;
path[i].y=0;
}
count_p=0;
gui = newtMyGUI();
}
tLabirint::~tLabirint()
{
delete gui;
}
voidtLabirint::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
{
for(j=1;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
{
for(j=1;j
printf("%d",a[i][j]);
printf("\n");
}
*/
}
inttLabirint::GetCommon(int i, int j, smezh &s)
{
//struct
tCoordscheck[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
{
if((check[k].x>0)&& (check[k].y>0) && (check[k].x
{
if(a[check[k].y][check[k].x]==1)
{
count++;
s[count].x=check[k].x;
s[count].y=check[k].y;
}
}
}
return count;
}
voidtLabirint::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
{
if(color[sm[i].y][sm[i].x]==0&& flag==0)
DFS_Visit(sm[i].y,sm[i].x);
}
color[y][x]=2;
}
voidtLabirint::DFS()
{
flag=0;
DFS_Visit(start.y,start.x);
}
voidtLabirint::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
gui->Line(sx+i*edge,sy, sx+i*edge, fy);
for(i=1;i
gui->Line(sx,sy+i*edge, fx, sy+i*edge);
for(i=1;i
{
for(j=1;j
{
if(a[i][j]==1)
gui->Fill(sx+(j*edge)-edge/ 2, sy+(i*edge)-edge / 2, RED);
}
}
}
voidtLabirint::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 = newtLabirint();
lab->ReadMatrix();
lab->DrawLabirint();
lab->Find();
/**/
getch();
delete lab;
}