Iniciar sesiónCerrar
Correo:
Contraseña:
Entrar
Recordar sesión en este navegador
Iniciar sesiónIniciar sesiónCrear cuentaCrear cuenta
LWP » Foros » Dev - C++ » Función en C++ que identifique "componentes conexas" de una matriz

Dev - C++ - Función en C++ que identifique "componentes conexas" de una matriz

Volver
Nuevo Tema
<<>>
 
Vista:

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

Publicado por Fernando Méndez (3 intervenciones) el 10/09/2020 14:54:32
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 {{0,1,1,1,0},{0,1,0,1,0},{0,1,1,1,0}} entonces al meterla como argumento en la función la matriz modificada debería ser {{2,1,1,1,3},{2,1,4,1,3},{2,1,1,1,3}}.
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:
1
2
3
4
5
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:
1
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í:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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 y leyendo el valor de las entradas , es decir, corrí el siguiente trozo de código para n=m=0:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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
1
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.
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
Imágen de perfil de Rodrigo
Val: 1.755
Plata
Ha mantenido su posición en Dev - C++ (en relación al último mes)
Gráfica de Dev - C++

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

Publicado por Rodrigo (539 intervenciones) el 10/09/2020 15:51:20
No se si lo que diga calce con el problema que tienes,
pero te sugiero que consideres esto y tal vez esto tenga que ver.

Voy a referirme al codigo que tiene los cout, el ultimo.

Las lineas 11, 17, 23 y 29, segun entiendo, intentan ver las posibilidades que existen hacia arriba, abajo, izquierda y derecha de la posicion que se establece en las lineas 5 y 6.

Tienes que tener cuidado con que los valores que se calculan en cada if esten dentro de los limites del arreglo. Algunas sumas estaran fuera de los limites (mas alla del final) y algunas restas seran negativas.

Te sugiero usar una funcion booleana tal vez para simplificar el codigo
Algo como:

1
2
3
if( vacia( carte, recpos.i, recpos.j+1 ) ) {
    ...
}

que devuelva true solo si los indices estan bien y el valor en la posicion indicada es 0.
o bien

1
2
3
if( posicion_valida( carte, recpos.i, recpos.j+1 ) &&  carte[recpos.i][recpos.j+1] == 0) {
    ...
}

pero asi parece mas largo el codigo.


Ese es el primer problema que veo.

El segundo problema que creo existe es que las lineas 14, 20 y 26 estan modificando la posicion que deberian considerar los siguientes ifs. Aunque es posible que el if de la linea 20 sea false siempre.

Dicho de otro modo, hablando en generico, si estas en la posicion x, y tus opciones DEBERIAN ser

x+1, y
x- 1, y
x, y + 1
x, y - 1

pero tus instrucciones en las lineas 14 y 26 hacen que las opciones se convierten en:

x + 1, y (se ingresa y se modifica la posicion)
x, y (por la modificacion hecha en la linea 14, y por lo hecho en la linea 7 no se ingresa al if)
x, y-1 y (se ingresa y se modifica la posicion)
x, y (por la modificacion hecha en la linea 26, y de nuevo, por lo hecho en la linea 7, no ingresa al if)

Si escribes los indices que estas evaluando en cada if creo que hara estos 2 problemas mas evidentes.

Eso creo que pasa.

Ojala vuelvas y corrobores que problema o problemas tenias.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

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

Publicado por Fernando Méndez (3 intervenciones) el 12/09/2020 20:37:09
Hola Rodrigo,
Muchísimas gracias por tus comentarios! Checaré con cuidado los puntos que mencionas :D.
Saludos!
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

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

Publicado por Fernando Méndez (3 intervenciones) el 06/02/2021 07:41:06
Hola de nuevo Rodrigo!
Tenías razón en todo, apenas tuve tiempo de corregir el programa. Dejaré la versión correcta aquí en caso de que le sirva a alguien en el futuro.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
void marque_composantes(Carte& carte)
{
	vector<Position> tableau_position;
	Position position,recpos;
	int composante(1);
	int l,k;
	int N,M;
	 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;
				  N=carte[n].size();
				  M=carte.size();
				  position={l,k};
				  tableau_position.push_back(position);
				  while (tableau_position.empty()==false){
					  recpos=tableau_position.back();
					  tableau_position.pop_back();
					  if (carte[recpos.i][recpos.j]==0){
						  carte[recpos.i][recpos.j]=composante;
						   if((recpos.i+1)<=(M-1)){
							  if(carte[recpos.i+1][recpos.j]==0){
							  tableau_position.push_back({recpos.i+1,recpos.j});
						  }
						  }
						  if((recpos.i-1)>=0){
							   if(carte[recpos.i-1][recpos.j]==0){
							  tableau_position.push_back({recpos.i-1,recpos.j});
						  }
						  }
						 if((recpos.j-1)>=0){
							 if(carte[recpos.i][recpos.j-1]==0){
							  tableau_position.push_back({recpos.i,recpos.j-1});
						  }
						 }
						  if((recpos.j+1)<=(N-1)){
							  if( carte[recpos.i][recpos.j+1]==0){
							   tableau_position.push_back({recpos.i,recpos.j+1});
						  }
						  }
 
 
 
 
					  }
 
 
 
				  }
			  }
			  }
		  }
 
}
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar