Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: alpachino98 en 8 Enero 2018, 13:08 pm


Título: AYUDA CON RECURSIVIDAD
Publicado por: alpachino98 en 8 Enero 2018, 13:08 pm
Hola buenas, tengo un problema con una función recursiva, se mete pero nunca sale. No se si tengo un error en la sintaxis o en la condición de parada. Si alguien ve algún fallo y puede ayudarme...Gracias

Código:
void FncOpenPoint(Tablero Partida, int fil, int col)
{
	if(fil>0&&fil<FIL&&col>0&&col<COL)
	{
	if(Partida[fil][col].mine==false)
		if(Partida[fil][col].num=0&&Partida[fil][col].flag==false)
		{
			Partida[fil][col].visible=true;
			/*for(int i=fil-1;i<fil+1;i++)
				for(int j=col-1;j<col+1;j++)
						FncOpenPoint( Partida,  fil,  col);	*/		
		   	FncOpenPoint( Partida,  fil-1,  col-1);
			 FncOpenPoint( Partida,  fil-1,  col);
			 FncOpenPoint( Partida,  fil-1,  col+1);
			 FncOpenPoint( Partida,  fil,  col-1);
			 FncOpenPoint( Partida,  fil,  col+1);
			 FncOpenPoint( Partida,  fil+1,  col-1);
			 FncOpenPoint( Partida,  fil+1,  col);
			 FncOpenPoint( Partida,  fil+1,  col+1);
		}
		else
			if(Partida[fil][col].mine!=true)
				Partida[fil][col].visible=true;		
	}
	return;
}
}

Como es un buscaminas tiene que ir recorriendo la matriz de forma recursiva hasta que encuentre una mina o llegue al limite del tablero. Se exige que sea de forma recursiva. Gracias

Título: Re: AYUDA CON RECURSIVIDAD
Publicado por: CalgaryCorpus en 8 Enero 2018, 13:44 pm
Supongo que es que estas chequeando que flag es false para continuar, pero no lo cambias nunca.

Cambialo. O usa visible, que si lo cambias.

Título: Re: AYUDA CON RECURSIVIDAD
Publicado por: do-while en 8 Enero 2018, 15:02 pm
Se te ha colado una asignación (=0) donde debería haber una comparacion (==0):
Código:
if(Partida[fil][col].num=0&&Partida[fil][col].flag==false)

El resto no lo he mirado.

Título: Re: AYUDA CON RECURSIVIDAD
Publicado por: alpachino98 en 8 Enero 2018, 15:15 pm
Cita de: do-while en  8 Enero 2018, 15:02 pm
Se te ha colado una asignación (=0) donde debería haber una comparacion (==0):
Código:
if(Partida[fil][col].num=0&&Partida[fil][col].flag==false)

El resto no lo he mirado.

Tienes razón pero sigue sin funcionar aún asi. La condición de parada es que encuentre los límites del tablero o que encuentre una mina. Pero hace dos cosas, solo me marca como visible la primera y no hace nada mas o se mete en bucle y no sale. Gracias!

Título: Re: AYUDA CON RECURSIVIDAD
Publicado por: MAFUS en 8 Enero 2018, 19:15 pm
Si nos pudieras decir qué es cada miembro de Partida, qué hace y cuáles son las condiciones de parada te podríamos ayudar mejor. Yo voy muy a ciegas.

Título: Re: AYUDA CON RECURSIVIDAD
Publicado por: alpachino98 en 8 Enero 2018, 19:44 pm
Cita de: MAFUS en  8 Enero 2018, 19:15 pm
Si nos pudieras decir qué es cada miembro de Partida, qué hace y cuáles son las condiciones de parada te podríamos ayudar mejor. Yo voy muy a ciegas.

Código:
struct Estados
{
	bool mine;
	bool visible=false;
	bool flag=false;
	int num=0;
	
};

Las condiciones de parada de la funcón recursiva son que encuentre una casilla con un valor diferente a 0 o encuentre una mina.

Título: Re: AYUDA CON RECURSIVIDAD
Publicado por: MAFUS en 8 Enero 2018, 20:03 pm
Vale, ya entiendo. Verás: tal y como está no se detendrá nunca porque visible no lo tienes en cuenta a la hora de parar. Imagina que tienes dos casillas contiguas que no tienen nada. El jugador marca la de la izquierda y la hace visible y el código pasa después a la de la derecha. El código la hace visible y en algún momento volverá a mirar la de la izquierda. Como no tiene condición de parada el que una casilla sea visible este bucle se repetira (izquierda, derecha, izquierda, derecha, ...) hasta que la pila se llene de llamadas y el programa se detenga.

Título: Re: AYUDA CON RECURSIVIDAD
Publicado por: alpachino98 en 8 Enero 2018, 20:31 pm
Cita de: MAFUS en  8 Enero 2018, 20:03 pm
Vale, ya entiendo. Verás: tal y como está no se detendrá nunca porque visible no lo tienes en cuenta a la hora de parar. Imagina que tienes dos casillas contiguas que no tienen nada. El jugador marca la de la izquierda y la hace visible y el código pasa después a la de la derecha. El código la hace visible y en algún momento volverá a mirar la de la izquierda. Como no tiene condición de parada el que una casilla sea visible este bucle se repetira (izquierda, derecha, izquierda, derecha, ...) hasta que la pila se llene de llamadas y el programa se detenga.

En eso creo que tienes toda la razón pero aun poniendo la condición de parada de visible sigue haciendo lo mismo de quitarme solo una si le asigno visible=true en el inicio o meterse en bucle si lo meto dentro de los ifs

Código:
void FncOpenPoint(Tablero Partida, int fil, int col)
{
	Partida[fil][col].visible=true;
	if(!Partida[fil][col].mine)
		if(Partida[fil][col].num==0&&!Partida[fil][col].flag&&!Partida[fil][col].visible)
		{
			//cout<<"yeee"<<endl;
			//Partida[fil][col].visible=true;
			//system("PAUSE");
			//do{
			if(fil>0||col>0){
			 FncOpenPoint( Partida,  fil-1,  col-1);
			 //cout<<"yeeeffffffffffffffffffffffffffffffffffffffffff"<<endl;
			 FncOpenPoint( Partida,  fil-1,  col);
			 FncOpenPoint( Partida,  fil-1,  col+1);
			 FncOpenPoint( Partida,  fil,  col-1);
			 FncOpenPoint( Partida,  fil,  col+1);
			 FncOpenPoint( Partida,  fil+1,  col-1);
			 FncOpenPoint( Partida,  fil+1,  col);
			 FncOpenPoint( Partida,  fil+1,  col+1);
			}//while (fil<0&&fil>FIL&&col<0&&col>COL);
			 /*for(int i=fil-1;i<fil+1;i++)
				for(int j=col-1;j<col+1;j++){
					FncOpenPoint( Partida,  i,  j);
					//cout<<"yeee"<<endl;
				}*/
		//system("PAUSE");
		}
		else{
			if(Partida[fil][col].mine!=true)
				Partida[fil][col].visible=true;	}	
}


Código:
void FncOpenPoint(Tablero Partida, int fil, int col)
{
	
	if(!Partida[fil][col].mine)
		if(Partida[fil][col].num==0&&!Partida[fil][col].flag&&!Partida[fil][col].visible)
		{
			//cout<<"yeee"<<endl;
			Partida[fil][col].visible=true;
			//system("PAUSE");
			//do{
			if(fil>0||col>0){
			 FncOpenPoint( Partida,  fil-1,  col-1);
			 //cout<<"yeeeffffffffffffffffffffffffffffffffffffffffff"<<endl;
			 FncOpenPoint( Partida,  fil-1,  col);
			 FncOpenPoint( Partida,  fil-1,  col+1);
			 FncOpenPoint( Partida,  fil,  col-1);
			 FncOpenPoint( Partida,  fil,  col+1);
			 FncOpenPoint( Partida,  fil+1,  col-1);
			 FncOpenPoint( Partida,  fil+1,  col);
			 FncOpenPoint( Partida,  fil+1,  col+1);
			}//while (fil<0&&fil>FIL&&col<0&&col>COL);
			 /*for(int i=fil-1;i<fil+1;i++)
				for(int j=col-1;j<col+1;j++){
					FncOpenPoint( Partida,  i,  j);
					//cout<<"yeee"<<endl;
				}*/
		//system("PAUSE");
		}
		else{
			if(Partida[fil][col].mine!=true)
				Partida[fil][col].visible=true;	}	
}

Título: Re: AYUDA CON RECURSIVIDAD
Publicado por: MAFUS en 9 Enero 2018, 00:18 am
Cosillas:
Toda la parte del else te sobra ya que
Código:
if(!Partida[fil][col].mine)
es lo mismo que
Código:
if(Partida[fil][col].mine!=true)

El primer código está mal ideado ya que visible valdrá true y no podrá entrar en el segundo if:
Código:
Partida[fil][col].visible=true;
if(!Partida[fil][col].mine)
  if(Partida[fil][col].num==0&&!Partida[fil][col].flag&&!Partida[fil][col].visible)

También veo que la función no está terminada pues buscas más allá de los límites de la tabla, tal vez te pierdes por allí. Como depuración haz que la función te diga en qué casilla se encuentra.

Título: Re: AYUDA CON RECURSIVIDAD
Publicado por: programerpro100%real en 9 Enero 2018, 01:41 am
He intentado solucionar tu problema pero me he atascado en lo mismo que tú, aunque no este solucionado, te pongo el código que he creado por si te puede servir de algo.
Código:
int i,j;
	
	Partida[fil][col].visible=true;		
	for (i=-1; i<2; i++)
		for (j=-1; j<2; j++)
			if (((fil+i>=0)&&(fil+i<FIL))&&((col+j>=0)&&(col+j<COL)))
				if (Partida[fil][col].visible == true)

                                   /* si la casilla tampoco tiene adyacentes se hace una llamada 
					recursiva */
					if (Partida[fil][col].visible == false&&Partida[fil][col].num==0){
						FncOpenPoint(Partida,fil+i,col+j);
					}
					else
						Partida[fil][col].visible=true;

				Partida[fil+i][col+j].visible = true;	
				}
}

Título: Re: AYUDA CON RECURSIVIDAD
Publicado por: MAFUS en 9 Enero 2018, 16:04 pm
Siguiendo tus premisas he hecho lo siguiente. Decir que no está probado y puede contener fallos.
Código
  1. void FncOpenPoint(Tablero Partida, int fil, int col) {
  2.     // Configuro los límites de búsqueda
  3.     int inicio_fil = fil==0? 0 : -1; // Si ya estoy arriba no debo mirar más arriba
  4.     int fin_fil = fil==FIL-1? 0 : 1; // Si ya estoy abajo no debo mirar más abajo
  5.     int inicio_col = col==0? 0 : -1; // Si ya estoy a la izquierda no debo mirar más a la izquierda
  6.     int fin_col = col==COL-1? 0 : 1; // Si ya estoy a la derecha no debo mirar más a la derecha
  7.     int i, j;
  8.  
  9.     if( !Partida[fil][col].visible &&
  10.         !Partida[fil][col].mine &&
  11.         !Partida[fil][col].num &&
  12.         !Partida[fil][col].flag ) {
  13.         Partida[fil][col].visible = true;
  14.  
  15.         for(i = inicio_fil; i <= fin_fil; ++i) {
  16.             for(j = inicio_col; j <= fin_col; ++j) {
  17.                 if(i==0 && j==0) continue; // Para no volver a caer en la casilla actual. Aunque es redundante no gasto tantos ciclos de reloj como si hay que realizar una llamada a la función en la misma coordenada y esperar a que esta se detenga por si sola.
  18.                 FncOpenPoint(Partida, fil+i, col+j);
  19.             }
  20.         }
  21.     }
  22. }

Título: Re: AYUDA CON RECURSIVIDAD
Publicado por: dijsktra en 7 Febrero 2018, 15:08 pm
A ver, vamos por partes.
En vez del buscaminas, hagamos una simplificación del problema para entenderlo mejor. Después solo lo adaptas al buscaminas (numeros, visible...)

De una matriz NxM de 0's y 1's, tenemos que dar una posición donde encontrar un 1. Nos vale cualquiera.

Código:
M=4, N=5
    0     i      M
    +--+--+--+--+
	   |  |  |  |  |
	   +--+--+--+--+
	   |1 |  |  |  |
	   +--+--+--+--+
	 j |  |  |  | 1|
	   +--+--+--+--+
	   |  |  |  |  |
	   +--+--+--+--+
	   |  |  |  |  |
	   +--+--+--+--+
          N

    Sol:  V[2][3]=1



Lo primero que te tienes que dar cuenta es de que la complejidad en el caso peor va a ser Omega(n^2) y no puedes bajar de ahí (imagina que está en la última casilla en el orden de  búsqueda).

Ahora viene la siguiente cuestión: se pide recursiva, de acuerdo, pero...
Por que no intenar dividiendo el tamaño del problema en  vez de sustrayendo?  

Me explico, se divide la matriz en cuatro cuadrantes A,B,C,D dividiendo sus dimensiones N,M por la mitad, y por recursión damos por resuelto el problema. Hay dos casos base posible:
  • matriz sin celdas, o vacía, donde nunca encuentras un 1. (significa que te has salido del rango)
  • matriz con UNA celda : si está, devolvemos cierto y las coordenadas de la celda. en otro caso falso y da igual las coordenadas

Imporante: En esta implementación siempre pensamos en el operador cortocircuitado OR... Es decir (true || a == 6 ) nunca pasa a evaluar la segunda expresi'on a==6. De otro modo, esto puede no funcionar. En la práctica, la mayoría de los compiladores proceden así, pero no se sabe si algun optimizador puede cambiar el orden.

Ahí va la solucion
Código
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. #define MAX 100
  6. /*
  7.   
  8. M=4, N=5
  9.            0     i      M
  10.            +--+--+--+--+
  11. 	   |  |  |  |  |
  12. 	   +--+--+--+--+
  13. 	   |1 |  |  |  |
  14. 	   +--+--+--+--+
  15. 	 j |  |  |  | 1|
  16. 	   +--+--+--+--+
  17. 	   |  |  |  |  |
  18. 	   +--+--+--+--+
  19. 	   |  |  |  |  |
  20. 	   +--+--+--+--+
  21.           N
  22.  
  23.     Sol:  V[2][3]=1
  24. */
  25.  
  26.  
  27. /*
  28.    Global inmersion
  29.    
  30.    P : V[j0..jn)[i0..in)
  31.        0<=i0<=in<=M, 0<=j0<=jn<=N
  32.    Q : found -> V[x][y]= 1
  33.  
  34.    B1 : empty square
  35.    B2 : one-cell square
  36.    C(i0,in,j0,j0) = (in-i0)*(jn-j0) (Area)
  37.    O(n^2), since A=4,B=2, k=0 and 4 > 2 
  38. */
  39. bool RR(const int V[][MAX],
  40. 	const int j0, const int jn, // N
  41. 	const int i0, const int in, // M
  42. 	int &x, int &y)
  43. {
  44.  
  45.   if (((in-i0)*(jn-j0)) == 0) // empty 
  46.     return false;
  47.   if (((in-i0)*(jn-j0)) == 1) // 1 cell 
  48.     {
  49.       x=j0;
  50.       y=i0;
  51.       return (V[x][y]==1);
  52.     }
  53.   else // 2 or more cells
  54.     {
  55.       const int hi = (in + i0) /2 ;
  56.       const int hj = (jn + j0) /2 ;
  57.       return
  58. 	(
  59. 	 RR(V,j0,hj,i0,hi,x,y) || RR(V,j0,hj,hi,in,x,y) ||
  60. 	 RR(V,hj,jn,i0,hi,x,y) || RR(V,hj,jn,hi,in,x,y)
  61. 	 );
  62.     }
  63. }  
  64.  
  65.  
  66.  
  67. /*
  68.    P : \exists i : 0 <= i<N , 0 <=j<M : V[i][j]=1
  69.  
  70.    Q : M[x][y]=1
  71.  
  72. */
  73. void R(const int V[][MAX],
  74.       const int N, const int M,
  75.        int &x, int &y)
  76. {
  77.   RR(V,0,N,0,M,x,y);
  78.   return;
  79. }
  80.  
  81.  
  82. int main()
  83. {
  84.   int V[MAX][MAX] ;
  85.   int n,N,m,M ;
  86.   int x,y;
  87.   cin >> N;
  88.   cin >> M;
  89.   for(int n=0; n<N; n++) 
  90.     for(int m=0; m<M; m++) cin >> V[n][m];
  91.   R(V,N,M,x,y);
  92.   cout << "(" << x << "," << y << ")" << endl;
  93.   return 0;
  94. }
  95.  

Algunos casos de prueba
Código:
6 5

0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0

Resultado
Código:
(0,2)


Otro

Código:
12 5

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Código:
(8,4)


Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines