ΠΠΎΠΈΡΠΊ Π² Π»Π°Π±ΠΈΡΠΈΠ½ΡΠ΅
Π‘ΡΠΈΡΡΠ²Π°Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ Π»Π°Π±ΠΈΡΠΈΠ½ΡΠ° ΠΈΠ· ΡΠ°ΠΉΠ»Π° ΠΠ°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΠ΅ Π΄ΠΎΡΡΡΠΏΠ½ΡΡ (ΡΠΌΠ΅ΠΆΠ½ΡΡ ) ΠΏΠΎΠ·ΠΈΡΠΈΠΉ Π² Π»Π°Π±ΠΈΡΠΈΠ½ΡΠ΅ (ΡΠ΅Ρ ΠΌΠ΅ΡΡ, ΠΊΡΠ΄Π° ΠΌΠΎΠΆΠ½ΠΎ Ρ ΠΎΠ΄ΠΈΡΡ) Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΏΠΎΠ·ΠΈΡΠΈΠΈ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ ΠΏΠΎΠΈΡΠΊΠ°. ΠΡΠ»ΠΈ ΠΏΠΎΠ·ΠΈΡΠΈΡ Π² Π»Π°Π±ΠΈΡΠΈΠ½ΡΠ΅ Π±Π΅Π»ΠΎΠ³ΠΎ ΡΠ²Π΅ΡΠ°, Ρ. Π΅. Π΅ΡΡ Π½ΠΈ ΡΠ°Π·Ρ Π½Π΅ ΠΏΠΎΠ΄Π²Π΅ΡΠ³Π°Π»Π°ΡΡ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠ΅ ΠΈ Π΅ΡΠ»ΠΈ Π½Π΅ Π΄ΠΎΡΡΠΈΠ³Π½ΡΡΠ° ΡΠΈΠ½Π°Π»ΡΠ½Π°Ρ ΠΏΠΎΠ·ΠΈΡΠΈΡ. ΠΠΎΠΈΡΠΊ Π² Π»Π°Π±ΠΈΡΠΈΠ½ΡΠ΅ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½ ΠΏΠΎΠΈΡΠΊΠΎΠΌ Π² Π³Π»ΡΠ±ΠΈΠ½Ρ (ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΠΎ) ΠΠ°Π½Π½Π°Ρ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½Π° Π² ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ΅ ΠΊΠ»Π°ΡΡΠΎΠΌ… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΠΎΠΈΡΠΊ Π² Π»Π°Π±ΠΈΡΠΈΠ½ΡΠ΅ (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
ΠΡΡΡΠΎΠ²Π°Ρ ΡΠ°Π±ΠΎΡΠ° ΠΏΠΎ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ
" ΠΠΎΠΈΡΠΊ Π² Π»Π°Π±ΠΈΡΠΈΠ½ΡΠ΅"
ΠΠΎΠΈΡΠΊ Π² Π³Π»ΡΠ±ΠΈΠ½Ρ:
ΠΠ»Π³ΠΎΡΠΈΡΠΌ
Π Π΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΏΠΎΠΈΡΠΊΠ°:
ΠΠΎΠΈΡΠΊ Π² Π»Π°Π±ΠΈΡΠΈΠ½ΡΠ΅ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½ ΠΏΠΎΠΈΡΠΊΠΎΠΌ Π² Π³Π»ΡΠ±ΠΈΠ½Ρ (ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΠΎ) ΠΠ°Π½Π½Π°Ρ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½Π° Π² ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ΅ ΠΊΠ»Π°ΡΡΠΎΠΌ 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-%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
#include
#include
#include
#include
#include
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;
}