0

Tengo la siguiente matriz:

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

Los 1's representan las "islas" (números seguidos verticalmente y horizontalmente), que se refiere a que se encuentran juntos. ¿Cómo puedo saber los que números están juntos y cuantas islas hay, de forma recursiva?

En este caso son 5 islas por lo siguiente:


1 - - - - -      - - - 1 - -      - - - - - -      - - - - - -      - - - - - -
- - - - - -      - - - - - -      - 1 - - - -      - - - - - -      - - - - - -
- - - - - -      - - - - - -      - 1 1 - - -      - - - - - -      - - - - - -
- - - - - -      - - - - - -      - - - - - -      - - - 1 1 1      - - - - - -
- - - - - -      - - - - - -      - - - - - -      - - - - 1 1      - 1 1 - - -

Tengo el siguiente código, pero sin recursividad (hace lo que se necesita pero no es recursivo) o se puede hacer recursivo el codigo?:

double conjuntoIslas(int a[][6]){
 int contCol, contFil, pivofil, pivocol, auxFil, auxCol;
 double sum = 0, island = 0;
 bool bol = false;
 contCol = 5;
 contFil = 4;
 while(contCol >= 0 && contFil >= 0){   
  if(a[contFil][contCol] == 1){
   pivofil = contFil;
        pivocol = contCol;
        auxFil = contFil;
        auxCol = contCol;

        cout<<endl<<endl<<"CUADRO EN: "<<contFil<<", "<<contCol<<endl;

        while(pivofil > 0){
            if(a[pivofil-1][pivocol] == 1){
                cout<<endl<<"\t"<<"Cuadro ARRIBA de: "<<pivofil<<", "<<pivocol;
                sum += 1;
                a[pivofil][pivocol] = 0;
                a[pivofil-1][pivocol] = 0;
                pivocol = auxCol;
                while(pivocol > 0){
                    if(a[pivofil-1][pivocol-1] == 1){
                        sum += 1;
                        cout<<endl<<"\t"<<"Cuadro IZQUIERDA de: "<<pivofil-1<<", "<<pivocol;
                        a[pivofil-1][pivocol-1] = 0;
                        pivocol--;
                    }
                    else{
                        pivocol = 0;
                    }
                }
                a[pivofil-1][pivocol] = 0;

                pivocol = auxCol;

                pivofil--;
            }
            else{
                pivofil = 0;
            }
        }
        pivofil = auxFil;
        while(pivocol > 0){
            if(a[pivofil][pivocol-1] == 1){
                cout<<endl<<"\t"<<"Cuadro a la IZQUIERDA de: "<<pivofil<<", "<<pivocol;
                sum += 1;
                a[pivofil][pivocol] = 0;
                a[pivofil][pivocol-1] = 0;
                pivofil = auxFil;
                while(pivofil > 0){
                    if(a[pivofil-1][pivocol-1] == 1){
                        cout<<endl<<"\t"<<"Cuadro ARRIBA de: "<<pivofil<<", "<<pivocol-1;
                        sum += 1;
                        a[pivofil-1][pivocol-1] = 0;
                        pivofil--;
                    }
                    else{
                        pivofil = 0;
                    }
                }
                pivofil = auxFil;
                a[pivofil][pivocol-1] = 0;
                pivocol--;
            }
            else{
                pivocol = 0;
            }
        }
        island += sum/sum;
        a[contFil][contCol] = 0;

    }
    if(contCol == 0){
        contFil--;
        contCol = 5;
    }
    else{
        contCol--;
    }
}
return island;
}
3
  • Podrías ser mas claro en tu problema y decir cual es el resultado esperado. el 3 jul. 2018 a las 5:06
  • Buenas noches, ya modifiqué la pregunta. A ver si se entiende un poco mas.
    – Bruno
    el 3 jul. 2018 a las 5:31
  • Bienvenido a Stack Overflow en español, te sugiero que hagas el recorrido de bienvenida para aprender el funcionamiento del sitio y de paso ganes tu primera medalla, también es muy importante que leas Cómo preguntar para poder mejorar tu pregunta y que esta sea bien recibida por la comunidad
    – ElGerar
    el 3 jul. 2018 a las 5:38

1 respuesta 1

3

Parece un caso adecuado para usar el Relleno por Difusión (Floodfill en Inglés). El pseudocódigo de ese algoritmo podría ser:

  1. Si la celda no está visitada.
    1. Marca la celda como visitada.
    2. Si la celda está ocupada.
      • Guarda la coordenada.
      • Visita la celda superior, inferior, izquierda y derecha.

Como puedes ver, el algoritmo es recursivo si se cumple el punto 2. La manera en que lo he implementado yo es en primer lugar creando un objeto de coordenadas y unos alias para facilitar la tarea:

struct coordenada { int x{}, y{}; };
using coordenadas = std::vector<coordenada>;
using islas = std::vector<coordenadas>;

Después creamos una función (plantilla) que reciba una formación1 bidimensional genérica sobre la que buscar islas:

template <int H, int W>
islas busca_islas(int (&matriz)[H][W])
{
    bool visitado[W][H]{};
    islas resultado{};

    for (int h = 0; h < W; ++h)
    {
        for (int v = 0; v < H; ++v)
        {
            coordenadas isla{};
            busca_islas({v, h}, isla, matriz, visitado);
            if (!isla.empty())
            {
                resultado.push_back(isla);
            }
        }
    }

    return resultado;
}

Las coordenadas v (vertical) y h (horizontal) están dadas la vuelta (las y antes que las x) porque int[6][6] significa seis filas de seis columnas no seis columnas de seis filas. Esta función que sólo recibe una formación de HxW (Height x Width) elementos llama a una sobrecarga que es la que hace la recursión:

template <int H, int W>
void busca_islas(const coordenada &c, coordenadas &resultado, int (&matriz)[H][W], bool (&visitado)[H][W])
{
    if (!visitado[c.y][c.x])
    {
        visitado[c.y][c.x] = true;

        if (matriz[c.y][c.x] == 1)
        {
            resultado.push_back(c);
            busca_islas({std::max(c.x - 1, 0), c.y}, resultado, matriz, visitado);
            busca_islas({std::min(c.x + 1, W - 1), c.y}, resultado, matriz, visitado);
            busca_islas({c.x, std::max(c.y - 1, 0)}, resultado, matriz, visitado);
            busca_islas({c.x, std::min(c.y + 1, H - 1)}, resultado, matriz, visitado);
        }
    }
}

Las llamadas a std::min y std::max son para no salirse de los rangos de la formación1.

Aplicando ese código sobre tus datos me salen las siguientes islas:

{ {0, 0} }
{ {3, 0} }
{ {1, 1} {1, 2} {2, 2} }
{ {3, 3} {4, 3} {5, 3} {5, 4} {4, 4} }
{ {1, 4} {2, 4} }

Que son las que buscabas. Puedes ver el código funcionando Aquí.


  1. También conocida como arreglo (o en inglés: array).

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.