laberinto recursivo

[Loco]

A ver, que esto está muy poco concurrido últimamente... para que os quebreis
un poco la cabeza, os presento una "chorradilla" que a mi me está dejando
las neuronas hipotecadas.





EL LABERINTO DEL LOCO



En la época clásica los griegos se tomaban la educación tan a pecho
que,según cuenta la leyenda, un profesor llamado Loco recluía en un
laberinto a sus alumnos más díscolos.



El laberinto tan solo tenía una salida a la cual sólo se podía acceder tras
resolver complicados problemas matemáticos, de tal manera que no eran pocos
los alumnos que perecían dentro del laberinto.



El laberinto estaba compuesto de habitaciones,muchas de ellas tenían tres
puertas que daban a otras tres habitaciones y otras eran habitaciones sin
salida.



Tenemos que realizar un programa que empezando por la habitación 0, vaya
buscando la salida a través de las puertas:



Primero pasa a la habitación a la que conduce la 1ª puerta y sigue buscando
la salida (abriendo puertas y entrando en las habitaciones...)



Si no encuentra la salida por ese camino vuelve hacia atrás y entra en la
habitación a la que conduce la tercera puerta.



Si no encuentra la salida por ninguna de las puertas(o la habitación no
tuviera puertas) volvería hacia atrás a la habitación por la que vino y
seguiría buscando por la puerta siguiente.



Representaremos el laberinto por una matriz de 20x3 en las que las filas
representan las habitaciones y las columnas son las habitaciones a la que
conducen las 3 puertas.



Ej)si la habitación 0 (fila 0), tiene estos valores: 1 2 4 significa que la
primera puerta conduce a la habitación 1, la segunda puerta conduce a la
habitación 2 y la tercera puerta conduce a la habitación 3.



Para representar una habitación que no tiene salida pondremos 100 100 100,
esto significa qu no conduce a ninguna habitación.



Para representar la puerta que conduce a la salida pondremos -1.



Los valores de la tabla que representan el laberinto son:



Int
laberinto[20][3]={1,2,4,5,3,11,100,100,100,100,100,100,6,3,1,100,100,100,5,7
,10,10,3,12,9,11,5,11,12,13,8,9,11,100,100,100,13,11,14,100,100,100,13,16,15
,13,11,16,19,13,18,19,13,-1,19,17,13,100,100,100};



El programa debe en cada momento ir informando de la busqueda, debe
escribier cuando entra en una habitación, indicando que habitacion es,
cuando abre una puerta y pasa a otra habitación, cuando se encuentra con una
habitación sin salida y cuando vuelve para atras para seguir buscando otro
camino.



El profesor Loco no era tan malo y según cuenta la leyenda siempre daba una
pista a sus alumnos antes de encerrarlos en el frío y lugubre laberinto...
"recursivoooo", les decia, "es mas fácil recursivoooooo"



Aunque las numerosas calaveras encontradas en excavaciones arqueológicas
parecen demostrar que, como suele ocurrir, los alumnos no le hacían
demasiado caso.



La cosa es que no me sale la maldita función esa, y mira que he gastado
folios y folios de planteamientos, pero la cosa no termina de cuadrar. Lo
máximo que he hecho en funciones recursivas es con dos caminos, pero tres no
llego a dominarlas, en especial en un caso como este. Al que se le vaya
ocurriendo alguna estructura, que la vaya poniendo, a modo de pista aunque
sea...



Loco.

[Fernando Arbeiza]

Post by Loco
La cosa es que no me sale la maldita función esa, y mira que he gastado
folios y folios de planteamientos, pero la cosa no termina de cuadrar. Lo
máximo que he hecho en funciones recursivas es con dos caminos, pero tres no
llego a dominarlas, en especial en un caso como este. Al que se le vaya
ocurriendo alguna estructura, que la vaya poniendo, a modo de pista aunque
sea...

Si no me equivoco, la cosa andaría por algo así:

/* ... */

que_paso_al entrar_a_habitacion(habitacion) {
for (i = 0; i < numero_puertas; i++) {
sorpresa = abrir_puerta(habitacion, i);
if (sorpresa == SALIDA) {
return CHACHI_ES_POR_AQUI;
} else if (sorpresa != NO_HAY_SALIDA) {
if (entrar_a_habitación(sorpresa) == CHACHI_ES_POR_AQUI) {
return CHACHI_ES_POR_AQUI;
}
}
}

return NO_ES_POR_AQUI_FURRO;
}

/* ... */

Un saludo.

[Loco]

Post by Fernando Arbeiza

Post by Loco
La cosa es que no me sale la maldita función esa, y mira que he gastado
folios y folios de planteamientos, pero la cosa no termina de cuadrar. Lo
máximo que he hecho en funciones recursivas es con dos caminos, pero tres no
llego a dominarlas, en especial en un caso como este. Al que se le vaya
ocurriendo alguna estructura, que la vaya poniendo, a modo de pista aunque
sea...

/* ... */
que_paso_al entrar_a_habitacion(habitacion) {
for (i = 0; i < numero_puertas; i++) {
sorpresa = abrir_puerta(habitacion, i);
if (sorpresa == SALIDA) {
return CHACHI_ES_POR_AQUI;
} else if (sorpresa != NO_HAY_SALIDA) {
if (entrar_a_habitación(sorpresa) == CHACHI_ES_POR_AQUI) {
return CHACHI_ES_POR_AQUI;
}
}
}
return NO_ES_POR_AQUI_FURRO;
}
/* ... */
Un saludo.

Perfecto, como pista. Pero aún así vas muy bien encaminado (según la
forma en que estaba implementando yo la función recursiva). De hecho,
gracias a un detalle tuyo, he conseguido resolverlo. Ahora solo me queda
que muestre el camino seguido, sin tener en cuenta las rutas
equivocadas, solo el camino directo a la salida...

L0C0.

[jakala]

buenas noches!!!

para eso piensa en "marcar en orden" el camino que vas siguiendo
desde el principio. Si tienes que "volver", tienes que "desmarcar" esa
posicion...

Jakala

Post by Loco

Post by Fernando Arbeiza

Post by Loco
La cosa es que no me sale la maldita función esa, y mira que he gastado
folios y folios de planteamientos, pero la cosa no termina de cuadrar. Lo
máximo que he hecho en funciones recursivas es con dos caminos, pero tres no
llego a dominarlas, en especial en un caso como este. Al que se le vaya
ocurriendo alguna estructura, que la vaya poniendo, a modo de pista aunque
sea...

/* ... */
que_paso_al entrar_a_habitacion(habitacion) {
for (i = 0; i < numero_puertas; i++) {
sorpresa = abrir_puerta(habitacion, i);
if (sorpresa == SALIDA) {
return CHACHI_ES_POR_AQUI;
} else if (sorpresa != NO_HAY_SALIDA) {
if (entrar_a_habitación(sorpresa) == CHACHI_ES_POR_AQUI) {
return CHACHI_ES_POR_AQUI;
}
}
}
return NO_ES_POR_AQUI_FURRO;
}
/* ... */
Un saludo.

Perfecto, como pista. Pero aún así vas muy bien encaminado (según la
forma en que estaba implementando yo la función recursiva). De hecho,
gracias a un detalle tuyo, he conseguido resolverlo. Ahora solo me queda
que muestre el camino seguido, sin tener en cuenta las rutas
equivocadas, solo el camino directo a la salida...
L0C0.

[Fernando Arbeiza]

Post by Loco
Perfecto, como pista. Pero aún así vas muy bien encaminado (según la
forma en que estaba implementando yo la función recursiva).

Eh, que conste que antes de publicarlo estaba comprobado ;-)

Post by Loco
Ahora solo me queda que muestre el camino seguido, sin tener en cuenta
las rutas equivocadas, solo el camino directo a la salida...

Ya te ha dicho Jakala como se hace. Sería algo así:

/* ... */

struct {
habitaciones;
puertas;
habitaciones_recorridas;
} solucion;

que_paso_al entrar_a_habitacion(habitacion, solucion) {
num_habitacion = solucion.habitaciones_recorridas;
solucion.habitaciones_recorridas++;

solucion.habitaciones[num_habitacion] = habitacion;
for (i = 0; i < numero_puertas; i++) {
solucion.puertas[num_habitacion] = i;
sorpresa = abrir_puerta(habitacion, i);
if (sorpresa == SALIDA) {
return CHACHI_ES_POR_AQUI;
} else if (sorpresa != NO_HAY_SALIDA) {
if (entrar_a_habitación(sorpresa, solucion) ==
CHACHI_ES_POR_AQUI) {
return CHACHI_ES_POR_AQUI;
}
}
}

solucion.habitaciones_recorridas--;
return NO_ES_POR_AQUI_FURRO;
}

/* ... */

Un saludo.

[Miguel]

#include <stdio.h>

static void Puerta(int, int);

#define HABITACIONES 20
#define PUERTAS 3
#define SALIDA -1
#define CERRADA 100

int laberinto[HABITACIONES][PUERTAS]={
{1,2,4},{5,3,11},
{100,100,100}, {100,100,100},
{6,3,1},{100,100,100},
{5,7,10},{10,3,12},
{9,11,5},{11,12,13},
{8,9,11},{100,100,100},
{13,11,14}, {100,100,100},
{13,16,15},{13,11,16},
{19,13,18},{19,13,-1},
{19,17,13},{100,100,100}};

int listo = 0;
int nueva = 1;

int main()
{
Puerta(0, 0);
return 0;
}


/*
*/
static void Puerta(int habitacion, int nivel)
{
int k;

for (k = 0; k < PUERTAS; k++)
{
int sighabita = laberinto[habitacion][k];
int n;

if (nueva)
{
for (n = 0; n < nivel; n++) printf(" ");
nueva = 0;
}
printf("%2d ", habitacion);

if (CERRADA != sighabita)
{
if (SALIDA == sighabita)
{
printf("%d\n", SALIDA);
listo = 1;
}
else Puerta(sighabita, nivel+1);
}
else
{
printf("%d\n", CERRADA);
nueva = 1;
return;
}
if (listo) return;
}
}

[Loco]

Post by Miguel
#include <stdio.h>
static void Puerta(int, int);
#define HABITACIONES 20
#define PUERTAS 3
#define SALIDA -1
#define CERRADA 100
int laberinto[HABITACIONES][PUERTAS]={
{1,2,4},{5,3,11},
{100,100,100}, {100,100,100},
{6,3,1},{100,100,100},
{5,7,10},{10,3,12},
{9,11,5},{11,12,13},
{8,9,11},{100,100,100},
{13,11,14}, {100,100,100},
{13,16,15},{13,11,16},
{19,13,18},{19,13,-1},
{19,17,13},{100,100,100}};
int listo = 0;
int nueva = 1;
int main()
{
Puerta(0, 0);
return 0;
}
/*
*/
static void Puerta(int habitacion, int nivel)
{
int k;
for (k = 0; k < PUERTAS; k++)
{
int sighabita = laberinto[habitacion][k];
int n;
if (nueva)
{
for (n = 0; n < nivel; n++) printf(" ");
nueva = 0;
}
printf("%2d ", habitacion);
if (CERRADA != sighabita)
{
if (SALIDA == sighabita)
{
printf("%d\n", SALIDA);
listo = 1;
}
else Puerta(sighabita, nivel+1);
}
else
{
printf("%d\n", CERRADA);
nueva = 1;
return;
}
if (listo) return;
}
}

Me parece que mandando a la primera función, solo recorres las
posibilidades de la primera puerta de la primera habitación, con lo que
te dejas todos los caminos de las otras dos puertas...
...creo...
...L0C0.

[Miguel]

Loco <***@ya.com> escribía,

[...]

Post by Loco
Me parece que mandando a la primera función, solo recorres las
posibilidades de la primera puerta de la primera habitación, con lo que
te dejas todos los caminos de las otras dos puertas...

No, la función abre todas las puertas que puedan abrirse y entra a todas
las habitaciones a las que puede entrarse, excepto aquellas puertas que
puedieran ser abiertas y habitaciones a las que pudiera entarse luego de
encontrar la salida.

Ok, el nombre de la función es un residuo del primer intento. Debería
tener uno mejor...

Post by Loco
...creo...

¡¡¡???

Tuviste problemas para compilarlo.

Post by Loco
...L0C0.

Saludos.

[Loco]

Post by Miguel
[...]

Post by Loco
Me parece que mandando a la primera función, solo recorres las
posibilidades de la primera puerta de la primera habitación, con lo que
te dejas todos los caminos de las otras dos puertas...

No, la función abre todas las puertas que puedan abrirse y entra a todas
las habitaciones a las que puede entrarse, excepto aquellas puertas que
puedieran ser abiertas y habitaciones a las que pudiera entarse luego de
encontrar la salida.
Ok, el nombre de la función es un residuo del primer intento. Debería
tener uno mejor...

Post by Loco
...creo...

¡¡¡???
Tuviste problemas para compilarlo.

Post by Loco
...L0C0.

Saludos.

No lo llegué a compilar. Tan solo que yo también empecé llamando a la
función pasándole la primera puerta de la primera habitación, y me di
cuenta que me dejaba las otras dos puertas. Lo solucioné preguntando si
el primer resultado era incorrecto, lo que hacía era llamar por segunda
vez a la función, pero pasándole la segunda puerta de la primera
habitación, y repitiendo la operación con la tercera puerta (que es por
donde al final hay que pasar...).
Como registro del camino recorrido, tan solo guardé las habitaciones y
sus respectivas puertas desde el momento de conseguir la salida a medida
que retrocedía, hasta llegar al principio, y mostrarlas en orden inverso.

De todas formas, mi algoritmo es un poco más largo que los vuestros,
porque después de varios intetntos y correciones sobre el anterior del
anterior del anterior... y tal, acabé haciendo un rebujo de tonterias
que todavçia no sé cómo conseguí la salida ni si todavía está terminado,
a pesar de que me de resultado. Por lo menos lo probé poniendo la salida
en diferentes sitios y me funcionaba...

L0C0.

PD: Ahí va lo que hice...

//Con Borland C/C++ 5.x bajo MS-DOS

#include <stdio.h>
#include <conio.h>
#define PARED 100
#define EXIT -1
#define TRUE 1
#define FALSE 0

typedef struct{
int habitacion;
int puerta;
}camino;

camino A[20]; //registro del camino recorrido
int casillas=0; //registro del número de casillas recorridas hasta el
//final
int i=0;


int lab[20][3]= //declarado el laberinto como global y listo
{1,2,4, //0
5,3,11, //1
100,100,100, //2
100,100,100, //3
6,3,1, //4
100,100,100, //5
5,7,10, //6
10,3,12, //7
9,11,5, //8
11,12,13, //9 indices
8,9,11, //10
100,100,100, //11
13,11,14, //12
100,100,100, //13
13,16,15, //14
13,11,16, //15
19,13,18, //16
19,13,-1, //17
19,17,13, //18
100,100,100}; //19

int Recorrer(int fil,int col);
int Valida(int fil,int col);

void main(void){
int ok;
int fil=0,col=0;
clrscr();
for(i=0;i<20;i++){//poner a 0 la tabla A
A[i].habitacion=A[i].puerta=0;
}
i=0;
ok=Recorrer(fil,col);
if(ok==TRUE){//por si la primera puerta sale rana
A[i].habitacion=fil;
A[i].puerta=col+1;
i++;
casillas++;
}
if(!ok){//idem de lo de rana
ok=Recorrer(fil,col+1);
if(ok==TRUE){
A[i].habitacion=fil;
A[i].puerta=col+1;
i++;
casillas++;
}
}
if(!ok){
ok=Recorrer(fil,col+2);
if(ok==TRUE){
A[i].habitacion=fil;
A[i].puerta=col+1;
i++;
casillas++;
}

}
if(!ok){
printf("No hay salida");
getch();
}
if(ok){
printf("Se ha encontrado la salida");
gotoxy(10,20);
for(i=0;i<casillas;i++){
printf("Habitaci¢n:%d
Puerta:%d\nn",A[i].habitacion,A[i].puerta);//imprime en orden inverso
}
}
getch();
}

int Valida(int fil,int col){
int resultado=TRUE;
if(lab[fil][col]==EXIT){
resultado=EXIT;
}
if(lab[fil][col]==PARED){
resultado=FALSE;
}
return resultado;
}

int Recorrer(int fil,int col){//mi super función recursiva
int listo=FALSE;
if(lab[fil][col]==EXIT){//primero preguntar si llego al final
//si llego, fin de la recursividad
//fin de la recursividad
gotoxy(10,12);
printf("la salida est en la habitaci¢n %d",fil);
gotoxy(10,13);
printf("en la puerta %d",col+1);
A[i].habitacion=fil;
A[i].puerta=col+1;
i++;
casillas++;
return TRUE;
}
if(lab[fil][col]==PARED){//pregunto si pared
listo=FALSE; //si lo es, vuelvo una posición
}
if(!listo&&Valida(lab[fil][col],0)){//puerta 0
listo=Recorrer(lab[fil][col],0);
if(listo==TRUE){
A[i].habitacion=fil;
A[i].puerta=col+1;
i++;
casillas++;
}
}
if(!listo&&Valida(lab[fil][col],1)){//puerta 1
listo=Recorrer(lab[fil][col],1);
if(listo==TRUE){
A[i].habitacion=fil;
A[i].puerta=col+1;
i++;
casillas++;
}

}
if(!listo&&Valida(lab[fil][col],2)){//puerta 2
listo=Recorrer(lab[fil][col],2);
if(listo==TRUE){
A[i].habitacion=fil;
A[i].puerta=col+1;
i++;
casillas++;
}

}
return listo;
}

[Fernando Arbeiza]

Post by Loco
PD: Ahí va lo que hice...
//Con Borland C/C++ 5.x bajo MS-DOS

Información que debería ser irrelevante, puesto que un programa tan
sencillo puede realizarse completamente con funciones estándar.

Post by Loco
#include <conio.h>

Como dije, ¿por qué utilizar funciones no estándar en este programa? Yo
no lo he compilado ni comprobado porque no tengo disponible esta
cabecera.

Post by Loco
camino A[20]; //registro del camino recorrido
int casillas=0; //registro del número de casillas recorridas hasta el
//final
int i=0;
int lab[20][3]= //declarado el laberinto como global y listo

Demasiadas variables globales. En un programa tan pequeño puede que no
te den problemas, pero acostúmbrate a restringir la visibilidad de las
variables. La única que podría dejar como global sería el laberinto, y
yo creo que ni eso.

Post by Loco
int lab[20][3]= //declarado el laberinto como global y listo
{1,2,4, //0
5,3,11, //1
/* ... */

La inicialización del laberinto quedaría más clara así:

{{1, 2, 4}, //0
{5, 3, 11}, //1
{100, 100, 100}, //2
{100, 100, 100}, //3
/* ... */

Post by Loco
void main(void){

main() debe devolver un int, es la definición más portable.

Post by Loco
clrscr();

Qué manía con borrar la pantalla al inicio de cada pantalla. Suele
hacerse gratuita e innecesariamente, como en este caso. La gente puede
tener datos en la consola que quiere conservar.

Post by Loco
for(i=0;i<20;i++){//poner a 0 la tabla A

La inicialización a 0 de A podías haberla hecho en su declaración. De
todas formas, ¿para qué la inicializas si puedes almacenar el número de
casillas recorridas?

Post by Loco
printf("No hay salida");

Utilizar printf() para imprimir cadenas de esa forma puede darte
problemas. Utiliza (f)puts() o la cadena de formato de printf().

Respecto al programa, es complicadísimo. Puede hacerse de forma muchos
más clara y más corta. Yo lo reescribiría, ahora que sabes cómo puede
hacerse.

Para iniciar el recorrido no hacen falta todos esos if, tendría que
valer con llamar a la función recursiva con la primera habitación como
argumento.

Un saludo.

[Loco]

Post by Fernando Arbeiza

Post by Loco
PD: Ahí va lo que hice...
//Con Borland C/C++ 5.x bajo MS-DOS

Información que debería ser irrelevante, puesto que un programa tan
sencillo puede realizarse completamente con funciones estándar.

Post by Loco
#include <conio.h>

Como dije, ¿por qué utilizar funciones no estándar en este programa? Yo
no lo he compilado ni comprobado porque no tengo disponible esta
cabecera.

Post by Loco
camino A[20]; //registro del camino recorrido
int casillas=0; //registro del número de casillas recorridas hasta el
//final
int i=0;
int lab[20][3]= //declarado el laberinto como global y listo

Demasiadas variables globales. En un programa tan pequeño puede que no
te den problemas, pero acostúmbrate a restringir la visibilidad de las
variables. La única que podría dejar como global sería el laberinto, y
yo creo que ni eso.

Post by Loco
int lab[20][3]= //declarado el laberinto como global y listo
{1,2,4, //0
5,3,11, //1
/* ... */

{{1, 2, 4}, //0
{5, 3, 11}, //1
{100, 100, 100}, //2
{100, 100, 100}, //3
/* ... */

Post by Loco
void main(void){

main() debe devolver un int, es la definición más portable.

Post by Loco
clrscr();

Qué manía con borrar la pantalla al inicio de cada pantalla. Suele
hacerse gratuita e innecesariamente, como en este caso. La gente puede
tener datos en la consola que quiere conservar.

Post by Loco
for(i=0;i<20;i++){//poner a 0 la tabla A

La inicialización a 0 de A podías haberla hecho en su declaración. De
todas formas, ¿para qué la inicializas si puedes almacenar el número de
casillas recorridas?

Post by Loco
printf("No hay salida");

Utilizar printf() para imprimir cadenas de esa forma puede darte
problemas. Utiliza (f)puts() o la cadena de formato de printf().
Respecto al programa, es complicadísimo. Puede hacerse de forma muchos
más clara y más corta. Yo lo reescribiría, ahora que sabes cómo puede
hacerse.
Para iniciar el recorrido no hacen falta todos esos if, tendría que
valer con llamar a la función recursiva con la primera habitación como
argumento.
Un saludo.

Muchas gracias por todos esos consejos. Serán tenidos en cuenta. Por el
resto, voy a descansar un poco que aunque sea la cosa sencillas como
dices, a mi me ha costao un rato sacar la cosa (entiéndase "cosa" como
este problema). Ya me esformaré un poco más cuando tenga más tiempo y
soltura en esto del C. Por cierto, hace poco me enteré de que "conio.h"
no era librería estándar. Sorry... bueno, en realidad no tengo la culpa,
pero bueno.

L0C0.

[Fernando Arbeiza]

Por el resto, voy a descansar un poco que aunque sea la cosa sencillas
como dices, a mi me ha costao un rato sacar la cosa (entiéndase "cosa"
como este problema).

Lo siento, no quería decir que el problema fuese sencillo. Si no tienes
un poco de experiencia en funciones recursivas el problema tiene su
miga.

Lo que quería decir es que le entrada/salida era sencilla y no
necesitabas la cabecera conio.h (es decir, entiéndase "cosa" sencilla
como entrada/salida ;-).

Ya me esformaré un poco más cuando tenga más tiempo y soltura en esto
del C.

Ya sabes, necesitas tres cosas: práctica, práctica y práctica. Bueno, y
un buen libro ("El lenguaje de Programación C", Segunda edición, de K&R,
por supuesto).

Por cierto, hace poco me enteré de que "conio.h" no era librería
estándar. Sorry... bueno, en realidad no tengo la culpa, pero bueno.

Pues no, no creo que tengas la culpa. En muchas partes se utiliza como
si fuese estándar, sin indicar que es específica de un sistema (que no
todos utilizamos :-)

Un saludo.