Курсовая работа по программированию
“Поиск в лабиринте”
Поиск в глубину:
Алгоритм
Реализация алгоритма поиска:
Поиск в лабиринте реализован поиском в глубину (рекурсивно)
Данная реализация представлена в программе классом 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-%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 <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: %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;
}
