سوال: الگوریتم maze با stack رو می خوام [بایگانی]

shask00l

یک شنبه 24 آبان 1388, 00:17 صبح

در مورد پیاده سازی اصولیش چیزی نمیدونم .... وقتی جوون بودم یه بار واسه خنده همینجوری پیاده سازی کردم

پیاده سازی که من انجام دادم به این صورت بود که :

یه ماتریس برای map داشتم + یه ماتریس خالی به همون اندازه که همه ی عناصرش صفر بود . تابع رو برای هر خونه ای که اجرا میکردم توی ماتریس دومی براش 1 میزاشتم . با توجه به مسیر توی ماتریس اول و خونه های 1 شده توی ماتریس دوم یه تابع بازشگتی اجرا میشد که از خونه ی اول شروع میکرد و تمام خونه های دورو بر رو چک میکرد ... به همین سادگی .

البته نمیدونم که این روش تا چه حد اصولیه ولی برای من که جواب داد

khazaie01

یک شنبه 24 آبان 1388, 19:52 عصر

#include<graphics.h>
#include<conio.h>
#include<dos.h>
#include<iostream.h>
struct Maze
{
int X, Y;
char Path; // 0 = starting, 1 = right , 2 = up , 3 = left , 4 = down
Maze *Next, *Parent;
} *Maze_Start = NULL, *Maze_Last = NULL;
int Environment[ 12 ][ 12 ] = {
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 },
{ 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0 },
{ 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0 },
{ 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0 },
{ 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0 },
{ 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0 },
{ 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0 },
{ 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0 },
{ 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1 },
{ 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0 },
{ 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0 },
{ 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0 } },
Y_Start = 1, X_Start = 0,
Y_End = 8, X_End = 11,
Bar_X, Bar_Y;
void ShowEnvironment();
int FindWay();
void ShowWay();
void DeleteNodes();
void main() {
int gdriver = DETECT, gmode;
initgraph( &gdriver, &gmode, "d:\\tc\\bgi" );
if( graphresult() != 0 )
{
cout<< "Graphics error \n"<<
"Press any key to halt:";
getch();
return;
}
ShowEnvironment();
outtextxy( 240, 20, " Press any key ! " );
getch();
Maze_Start = Maze_Last = new Maze;
Maze_Start->X = X_Start;
Maze_Start->Y = Y_Start;
Maze_Start->Path = 0;
Maze_Start->Parent = NULL;
while( 1 )
{
if( Maze_Last->X == X_End && Maze_Last->Y == Y_End )
{
ShowWay();
outtextxy( 19, 45, " OK " );
break;
}
if( FindWay() == 0 )
{
outtextxy( 19, 45, " Failed " );
break;
}
}
DeleteNodes();
getch();
closegraph();
}
void ShowEnvironment()
{
int X, Y;
setbkcolor( LIGHTGRAY );
setfillstyle( SOLID_FILL, CYAN );
X = Bar_X = getmaxx() / 2 - 180;
Y = Bar_Y = getmaxy() / 2 - 180;
bar( X, Y, X + 360, Y + 360 );
setcolor( DARKGRAY );
rectangle( X - 1, Y - 1, X + 361, Y + 361 );
setfillstyle( SOLID_FILL, BLUE );
for( int i = 0; i < 12; i++ )
{
for( int j = 0; j < 12; j++ )
{
if( Environment[ i ][ j ] == 1 )
bar( X, Y, X + 30, Y + 30 );
X += 30;
}
Y += 30;
X = getmaxx() / 2 - 180;
}
setcolor( BLACK );
setfillstyle( SOLID_FILL, MAGENTA );
fillellipse( Bar_X + X_End * 30 + 15, Bar_Y + Y_End * 30 + 15, 10, 10 );
setcolor( BLUE );
setfillstyle( SOLID_FILL, RED );
fillellipse( Bar_X + X_Start * 30 + 15, Bar_Y + Y_Start * 30 + 15, 10, 10 );
}
int FindWay()
{
int X = Maze_Last->X,
Y = Maze_Last->Y;
while( 1 )
{
if( ++Maze_Last->Path == 5 )
{
setfillstyle( SOLID_FILL, BLUE );
fillellipse( Bar_X + Maze_Last->X * 30 + 15, Bar_Y + Maze_Last->Y * 30 + 15, 10, 10 );
Environment[ Maze_Last->Y ][ Maze_Last->X ] = 1;
Maze * temp = Maze_Last;
Maze_Last = Maze_Last->Parent;
Maze_Last->Next = NULL;
delete temp;
if( Maze_Last == NULL ) return 0;
X = Maze_Last->X;
Y = Maze_Last->Y;
setfillstyle( SOLID_FILL, RED );
fillellipse( Bar_X + Maze_Last->X * 30 + 15, Bar_Y + Maze_Last->Y * 30 + 15, 10, 10 );
delay( 200 );
continue;
}
switch( Maze_Last->Path )
{
case 1 :
if( ( Maze_Last->Parent != NULL && Maze_Last->Parent->Path == 3 ) || Environment[ Y ][ X + 1 ] == 0 || X + 1 > 11 ) continue;
X ++;
break;
case 2 :
if( ( Maze_Last->Parent != NULL && Maze_Last->Parent->Path == 4 ) || Environment[ Y - 1 ][ X ] == 0 || Y - 1 < 0 ) continue;
Y --;
break;
case 3 :
if( ( Maze_Last->Parent != NULL && Maze_Last->Parent->Path == 1 ) || Environment[ Y ][ X - 1 ] == 0 || X - 1 < 0 ) continue;
X --;
break;
case 4 :
if( ( Maze_Last->Parent != NULL && Maze_Last->Parent->Path == 2 ) || Environment[ Y + 1 ][ X ] == 0 || Y + 1 > 11 ) continue;
Y ++;
}
setfillstyle( SOLID_FILL, BLUE );
fillellipse( Bar_X + Maze_Last->X * 30 + 15, Bar_Y + Maze_Last->Y * 30 + 15, 10, 10 );
Maze_Last->Next = new Maze;
Maze_Last->Next->X = X;
Maze_Last->Next->Y = Y;
Maze_Last->Next->Path = 0;
Maze_Last->Next->Parent = Maze_Last;
Maze_Last->Next->Next = NULL;
Maze_Last = Maze_Last->Next;
Environment[ Y ][ X ] = 0;
setfillstyle( SOLID_FILL, RED );
fillellipse( Bar_X + Maze_Last->X * 30 + 15, Bar_Y + Maze_Last->Y * 30 + 15, 10, 10 );
delay( 200 );
return 1;
}
}
void ShowWay()
{
Maze *temp = Maze_Last->Parent;
setcolor( DARKGRAY );
while( temp != NULL )
{
outtextxy( Bar_X + temp->X * 30 + 10, Bar_Y + temp->Y * 30 + 10, "±" );
temp = temp->Parent;
}
setcolor( BLUE );
}
void DeleteNodes()
{
Maze *temp = Maze_Start;
while( Maze_Start )
{
Maze_Start = Maze_Start->Next;
delete temp;
temp = Maze_Start;
}
}