AYUDA CON RECURSIVIDAD página 2

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

#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:

Resultado

Código:

(0,2)

Otro

Código:

Código:

(8,4)