Autor Tema: Función en C++ que identifique "componentes conexas" de una matriz

0 Usuarios y 1 Visitante están viendo este tema.

08 Septiembre, 2020, 10:23 pm
Leído 161 veces

FerOliMenNewton

  • Aprendiz
  • Mensajes: 223
  • País: mx
  • Karma: +0/-0
  • Sexo: Masculino
Hola a todos, espero estén bien.
Me interesa hacer una función en C++ que dada una matriz rectangular que sólo contiene ceros y unos, la recorra de izquierda a derecha marcando con un número(2 para la primera zona conexa, 3 para la siguiente zona conexa, etc) cada zona conexa donde haya ceros, por ejemplo, si tenemos la matriz
\( \begin{bmatrix}{0}&{1}&{1}&{1}&{0}\\{0}&{1}&{0}&{1}&{0}\\{0}&{1}&{1}&{1}&{0}\end{bmatrix}  \)
entonces al meterla como argumento en la función la matriz modificada debería ser
\( \begin{bmatrix}{2}&{1}&{1}&{1}&{3}\\{2}&{1}&{4}&{1}&{3}\\{2}&{1}&{1}&{1}&{3}\end{bmatrix}  \)
Para ello lo primero que hice fue definir una estructura que contiene dos campos: uno para el índice de la fila 'i' y otro para el índica de la columna 'j', es decir definí lo siguiente:
struct Position
{
   int i;
   int j;
};

Asimismo para simplificar la "notación" en el programa para las matrices, les dí el alias "Carte" con las siguientes líneas:
typedef vector<vector<int>> Carte;
Finalmente, en la definición de la función hice lo siguiente(adjuntaré el código al final):
1. Declaré un vector dinámico del tipo Position(la estructura que definí arriba), para que me ayude a almacenar las entradas que esté tratando. Lo llamé 'vector_position'.
2. Declaré una variable del tipo entero inicializada en 1 que me ayude a etiquetar las zonas conexas de ceros.  La llamé 'composante'.
3. Usé dos ciclos for que recorriera la matriz de izquierda a derecha tal que:
    3.1 Si la entrada \( (i,j)=0 \) aumentará en 1 la variable 'composante' y después de eso añadimos la entrada \( (i,j) \) al vector dinámico, luego , mientras éste vector dinámico no esté vacío:
      3.1.1 Suprimir y recuperar el valor de el último elemento del vector, y fijarme en las entradas que estén al norte, este, oeste, y sur de esta posición, y si alguna de ellas es cero pues cambiar el valor cero por el valor de la variable 'composante' y añadir estas entradas al vector.
Él código me quedó así:
void marque_composantes(Carte& carte)
{
   vector<Position> tableau_position;
   Position position,recpos;
   int composante(1);
   int l,k;
    for (size_t n(0); n< carte.size();n++){
        for (size_t m(0); m< carte[n].size() ;m++){
           if(carte[n][m]==0){
              composante++;
              l=n;
              k=m;
              position={l,k};
              tableau_position.push_back(position);
              carte[n][m]=composante;
              while (tableau_position.empty()==false){
                 recpos=tableau_position.back();
                 tableau_position.pop_back();
                    if(carte[recpos.i+1][recpos.j]==0){
                       carte[recpos.i+1][recpos.j]=composante;
                       recpos.i=recpos.i+1;
                       tableau_position.push_back(recpos);
                    }
                    if(carte[recpos.i-1][recpos.j]==0){
                       carte[recpos.i-1][recpos.j]=composante;
                       recpos.i=recpos.i-1;
                       tableau_position.push_back(recpos);
                    }
                    if(carte[recpos.i][recpos.j-1]==0){
                       carte[recpos.i][recpos.j-1]=composante;
                       recpos.j=recpos.j-1;
                       tableau_position.push_back(recpos);
                    }
                    if( carte[recpos.i][recpos.j+1]==0){
                        carte[recpos.i][recpos.j+1]=composante;
                        recpos.j=recpos.j+1;
                        tableau_position.push_back(recpos);
                    }
              }
           }
           }
        }
   
}   
 
Para probar qué tan correcto era el código fui imprimiendo entradas aleatorias pero la terminal NO imprime nada :( . Así que para ver dónde estaba el error supuse \( n=m=0 \) y tomé la matriz del ejemplo que les puse, añadí algunos comandos "cout" dentro de los 'if' para ir verificando el valor de las entradas , es decir, corrí el siguiente trozo de código para \( n=m=0 \):
if(carte[n][m]==0){
              composante++;
              l=n;
              k=m;
              position={l,k};
              tableau_position.push_back(position);
              carte[n][m]=composante;
              while (tableau_position.empty()==false){
                 recpos=tableau_position.back();
                 tableau_position.pop_back();
                    if(carte[recpos.i+1][recpos.j]==0){
                       carte[recpos.i+1][recpos.j]=composante;
                       cout << "carte[" << recpos.i+1 << "]" << "[" << recpos.j << "]" << "=" << carte[recpos.i+1][recpos.j] << endl;
                       recpos.i=recpos.i+1;
                       tableau_position.push_back(recpos);
                    }
                    if(carte[recpos.i-1][recpos.j]==0){
                       carte[recpos.i-1][recpos.j]=composante;
                       cout << "carte[" << recpos.i-1 << "]" << "[" << recpos.j << "]" << "=" << carte[recpos.i-1][recpos.j] << endl;
                       recpos.i=recpos.i-1;
                       tableau_position.push_back(recpos);
                    }
                    if(carte[recpos.i][recpos.j-1]==0){
                       carte[recpos.i][recpos.j-1]=composante;
                       cout << "carte[" << recpos.i << "]" << "[" << recpos.j-1 << "]" << "=" << carte[recpos.i][recpos.j-1] << endl;
                       recpos.j=recpos.j-1;
                       tableau_position.push_back(recpos);
                    }
                    if( carte[recpos.i][recpos.j+1]==0){
                        carte[recpos.i][recpos.j+1]=composante;
                        cout << "carte[" << recpos.i << "]" << "[" << recpos.j+1 << "]" << "=" << carte[recpos.i][recpos.j+1] << endl;
                        recpos.j=recpos.j+1;
                        tableau_position.push_back(recpos);
                    }
              }
           }

Pero al correrlo, noté que las entradas estaban cambiando justo como yo quería(y lo sé porque me las está imprimiendo) que cambiarán pero al añadir por ejemplo la siguiente línea al final del código anterior
cout << "carte[0][0]=" << carte[n][m] << endl;
Pues la terminal imprime todo EXCEPTO la línea anterior, es decir: si no pongo los "cout" dentro de los if seguiría sin imprimir nada, por qué pasa esto? xD Podrían explicarme por favor?
Muchas gracias.
Saludos cordiales.

12 Septiembre, 2020, 12:54 am
Respuesta #1

ingmarov

  • Moderador Global
  • Mensajes: 4,799
  • País: hn
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Debería imprimir lo que quieres, esta raro este problema. A seguir revisando.

Saludos
No te confíes, revisa lo que escribo. Yo también me equivoco.
Odio el autocorrector de Android...

12 Septiembre, 2020, 05:48 pm
Respuesta #2

FerOliMenNewton

  • Aprendiz
  • Mensajes: 223
  • País: mx
  • Karma: +0/-0
  • Sexo: Masculino
Hola ingmarov, gracias por tu respuesta. Si está un poco extraño, tendré que seguir pensando :) , a lo mejor se me está pasando algo.
Saludos.