AYUDA CON RECURSIVIDAD

[MAFUS]

Siguiendo tus premisas he hecho lo siguiente. Decir que no está probado y puede contener fallos.

Código (c++) [Seleccionar] Expandir

void FncOpenPoint(Tablero Partida, int fil, int col) {
   // Configuro los límites de búsqueda
   int inicio_fil = fil==0? 0 : -1; // Si ya estoy arriba no debo mirar más arriba
   int fin_fil = fil==FIL-1? 0 : 1; // Si ya estoy abajo no debo mirar más abajo
   int inicio_col = col==0? 0 : -1; // Si ya estoy a la izquierda no debo mirar más a la izquierda
   int fin_col = col==COL-1? 0 : 1; // Si ya estoy a la derecha no debo mirar más a la derecha
   int i, j;
   
   if( !Partida[fil][col].visible &&
       !Partida[fil][col].mine &&
       !Partida[fil][col].num &&
       !Partida[fil][col].flag ) {
       Partida[fil][col].visible = true;
       
       for(i = inicio_fil; i <= fin_fil; ++i) {
           for(j = inicio_col; j <= fin_col; ++j) {
               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.
               FncOpenPoint(Partida, fil+i, col+j);
           }
       }
   }
}

[dijsktra]

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 [Seleccionar] Expandir


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 (c) [Seleccionar] Expandir


#include <iostream>

using namespace std;

#define MAX 100
/*
 
M=4, N=5
          0     i      M
          +--+--+--+--+
  |  |  |  |  |
  +--+--+--+--+
  |1 |  |  |  |
  +--+--+--+--+
j |  |  |  | 1|
  +--+--+--+--+
  |  |  |  |  |
  +--+--+--+--+
  |  |  |  |  |
  +--+--+--+--+
         N

   Sol:  V[2][3]=1
*/


/*
  Global inmersion
 
  P : V[j0..jn)[i0..in)
      0<=i0<=in<=M, 0<=j0<=jn<=N
  Q : found -> V[x][y]= 1

  B1 : empty square
  B2 : one-cell square
  C(i0,in,j0,j0) = (in-i0)*(jn-j0) (Area)
  O(n^2), since A=4,B=2, k=0 and 4 > 2
*/
bool RR(const int V[][MAX],
const int j0, const int jn, // N
const int i0, const int in, // M
int &x, int &y)
{

 if (((in-i0)*(jn-j0)) == 0) // empty
   return false;
 if (((in-i0)*(jn-j0)) == 1) // 1 cell
   {
     x=j0;
     y=i0;
     return (V[x][y]==1);
   }
 else // 2 or more cells
   {
     const int hi = (in + i0) /2 ;
     const int hj = (jn + j0) /2 ;
     return
(
RR(V,j0,hj,i0,hi,x,y) || RR(V,j0,hj,hi,in,x,y) ||
RR(V,hj,jn,i0,hi,x,y) || RR(V,hj,jn,hi,in,x,y)
);
   }
}  



/*
  P : \exists i : 0 <= i<N , 0 <=j<M : V[i][j]=1

  Q : M[x][y]=1

*/
void R(const int V[][MAX],
     const int N, const int M,
      int &x, int &y)
{
 RR(V,0,N,0,M,x,y);
 return;
}


int main()
{
 int V[MAX][MAX] ;
 int n,N,m,M ;
 int x,y;
 cin >> N;
 cin >> M;
 for(int n=0; n<N; n++)
   for(int m=0; m<M; m++) cin >> V[n][m];
 R(V,N,M,x,y);
 cout << "(" << x << "," << y << ")" << endl;
 return 0;
}


Algunos casos de prueba

Código [Seleccionar] Expandir

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 [Seleccionar] Expandir


(0,2)



Otro

Código [Seleccionar] Expandir


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 [Seleccionar] Expandir

(8,4)