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