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;

}

Страницы: 1, 2