Тип координат.
Представляет собой структуру с двумя полями 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;
}