Caiman
04 de Mayo del 2004

Estoy realizando un programa que haga laberintos, con la programacion no hay problema pero me quede atorado en la fase de planeación, pues no se como o que metodo usar para hacer que la computadora realice el laberinto con un camino que lo recorra tenga entrada y salida.
Si me pueden decir por donde puedo empezar?

noel solw
04 de Mayo del 2004

Te envio dos programas que trabajan con labertintos :
uno recursivo y el otro no.

[a] : programa no recursivo

// program k5a7.CPP - page 79
// labyrinth.
// c++ exercices book - dr. gershon kagan (first edition : 2001)
// written in Borland CPP ver 3.1

#include <conio.h>
#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#include <dos.h>

#define M 12
#define N 10
#define B (80-3*N)/2
#define H (24-M)/2
#define CLOCK 1
#define ANTICLOCK -1
#define north 0
#define east 1
#define south 2
#define west 3

const char *sym[] = {"²²²"," ù "," þ "};
const color[] = {LIGHTBLUE,YELLOW,LIGHTRED};

void ShowLabyrinth(char a[M+2][N+2])
{
gotoxy(B+10,3);
cout << "Labyrinth Maze";
textcolor(color[0]);
for(int i = 0; i < M+2; i++)
{
gotoxy(B,H+i);
for(int j = 0; j < N+2; j++)
cprintf(sym[a[i][j]]);
cout << endl;
}
cout << endl;
} // SHOW LABYRINTH

int OutSide(int i,int j)
{
return (i == 0) || (i == M+1) || (j == 0) || (j == N+1);
} // OUTSIDE

void Show(int i,int j,int sw)
{
gotoxy(B+j*3,H+i);
textcolor(color[sw]);
cprintf(sym[sw]);
} // SHOW

int LeftEmpty(char a[M+2][N+2],int i,int j,int dir)
{
int ret;
switch(dir)
{
case north : ret = a[i][j-1];
break;
case east : ret = a[i-1][j];
break;
case south : ret = a[i][j+1];
break;
case west : ret = a[i+1][j];
break;
}
return ret;
} // LEFT EMPTY

int FrontEmpty(char a[M+2][N+2],int i,int j,int dir)
{
int ret;
switch(dir)
{
case north : ret = a[i-1][j];
break;
case east : ret = a[i][j+1];
break;
case south : ret = a[i+1][j];
break;
case west : ret = a[i][j-1];
break;
}
return ret;
} // FRONT EMPTY

int Rotate(int dir,int clock)
{
dir += clock + 4;
return dir % 4;
} // ROTATE

void Process(char a[M+2][N+2])
{
int i = 2, j = 0,di,dj;
int dir = east;
char choice = 100;
Show(i,j++,1);
Show(i,j,2);
while(!OutSide(i,j) && choice != 27)
{
delay(150);
Show(i,j,1);
if(LeftEmpty(a,i,j,dir))
{
dir = Rotate(dir,ANTICLOCK);
if(!FrontEmpty(a,i,j,dir))
dir = Rotate(dir,CLOCK);
}
if(!FrontEmpty(a,i,j,dir))
{
dir = Rotate(dir,CLOCK);
if(!FrontEmpty(a,i,j,dir))
dir = Rotate(dir,CLOCK);
}
switch(dir)
{
case north : di = -1;
dj = 0;
break;
case east : di = 0;
dj = 1;
break;
case south : di = 1;
dj = 0;
break;
case west : di = 0;
dj = -1;
break;
}
i += di;
j += dj;
Show(i,j,2);
if(kbhit())
choice = getch();
}
} // PROCESS

void main()
{
char a[M+2][N+2] = {{1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,0,1},
{1,1,1,0,1,1,1,1,1,1,0,1},
{1,0,1,0,0,1,0,0,0,1,0,1},
{1,0,1,1,0,1,0,1,1,1,0,1},
{1,0,1,0,0,1,0,0,0,0,0,1},
{1,0,1,0,1,1,1,1,1,1,0,1},
{1,0,1,0,1,0,1,0,0,1,0,1},
{1,0,1,0,0,0,1,0,0,1,0,1},
{1,0,1,1,1,0,1,1,1,1,0,1},
{1,0,0,0,1,1,1,0,0,0,0,1},
{1,0,1,1,1,0,1,1,1,1,0,1},
{1,0,0,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1}};
randomize();
int x = random(3),i = random(M-2)+2;
switch(x)
{
case 0 :
case 1 : int j = 1;
if(a[i][j+1])
a[i][j] = 1;
break;
case 2 : j = N;
if(a[i][j-1])
a[i][j] = 1;
}
clrscr();
_setcursortype(_NOCURSOR);
ShowLabyrinth(a);
Process(a);
gotoxy(B+3,23);
cout << "end of program - good bye ! ! !n";
getch();
_setcursortype(_NORMALCURSOR);
} // MAIN

noel solw
04 de Mayo del 2004

[b] : programa recursivo

// program k7c3 - page 135.
// recursive labyrinth.
// c++ exercices book - dr. gershon kagan - first edition : 2001
// written in Borland CPP ver 3.1

#include <conio.h>
#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#include <dos.h>

#define M 12
#define N 10
#define B (80-3*N)/2
#define H (24-M)/2

const char *sym[] = {"²²²"," ù "," þ "};
const color[] = {LIGHTBLUE,YELLOW,LIGHTRED,LIGHTMAGENTA};

void ShowLabyrinth(char a[M+2][N+2])
{
gotoxy(B+10,3);
textcolor(color[3]);
cprintf("Labyrinth Maze");
textcolor(color[0]);
for(int i = 0; i < M+2; i++)
{
gotoxy(B,H+i);
for(int j = 0; j < N+2; j++)
cprintf(sym[a[i][j]]);
cout << endl;
}
cout << endl;
} // SHOW LABYRINTH

int OutSide(int i,int j)
{
return (i == 0) || (i == M+1) || (j == 0) || (j == N+1);
} // OUTSIDE

void Show(int i,int j,int sw)
{
gotoxy(B+j*3,H+i);
textcolor(color[sw]);
cprintf(sym[sw]);
delay(150);
} // SHOW

void Write(int i,int j)
{
static int y = 1,
x = 2;
gotoxy(x,y++);
if(y > 23)
{
x += 8;
y = 1;
}
textcolor(LIGHTGRAY);
cprintf("(%d,%d)",i+1,j+1);
}

int Process(char a[M+2][N+2],int i,int j)
{
if(!a[i][j])
return 0;
Show(i,j,1);
if(!i || !j || i == M+1 || j == N+1)
{
Show(i,j,2);
Write(i,j);
return 1;
}
a[i][j] = 0;
int ret = Process(a,i-1,j) || Process(a,i+1,j) ||
Process(a,i,j+1) || Process(a,i,j-1);
if(ret)
{
Show(i,j,2);
Write(i,j);
}
return ret;
} // PROCESS

void main()
{
char a[M+2][N+2] = {{1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,0,1},
{1,1,1,1,0,0,1,1,1,1,1,1},
{1,0,0,1,0,1,1,0,0,1,0,1},
{1,0,0,1,0,0,1,0,0,0,0,1},
{1,0,0,1,0,1,1,1,1,1,0,1},
{1,0,1,1,0,0,1,0,0,1,0,1},
{1,0,1,0,0,0,1,0,0,1,0,1},
{1,0,1,1,1,1,1,0,0,1,0,1},
{1,0,0,0,1,0,1,1,1,1,0,1},
{1,0,1,0,1,0,1,0,0,0,0,1},
{1,0,1,1,1,0,1,1,1,1,0,1},
{1,0,0,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1}};
clrscr();
_setcursortype(_NOCURSOR);
ShowLabyrinth(a);
Show(2,0,1);
a[2][0] = 0;
if (Process(a,2,1))
{
Show(2,0,2);
Write(2,0);
}
else
{
gotoxy(B+10,21);
textcolor(color[3]);
cprintf("path not found");
}
gotoxy(B+3,23);
textcolor(color[3]);
cprintf("end of program - good bye ! ! !n");
getch();
_setcursortype(_NORMALCURSOR);
textcolor(WHITE);
} // MAIN