Iniciar sesiónCerrar
Correo:
Contraseña:
Entrar
Recordar sesión en este navegador
Iniciar sesiónIniciar sesiónCrear cuentaCrear cuenta
LWP » Foros » Java » Que esta fallando?

Java - Que esta fallando?

Volver
Nuevo Tema
<<>>
 
Vista:

Que esta fallando?

Publicado por Pedro (1 intervención) el 13/09/2022 21:15:39
A partir de una Matriz de unos y ceros, debo validar si la misma tiene al menos un cuadrado con vertices de 1, aqui van algunos ejemplos validos:
101
000
101


1 1 1
1 1 1
1 1 1

00011
00011
00000


00101
00101
00000


Aqui van otros ejemplos No validos:


00
00

01
00

00011
00010

La matriz puede tener cualquier dimension.

Esto es lo que hice:

public static Boolean hayCuadrado (char [][] mat){
int filas;
int columnas;
filas= mat.length;
columnas = mat[0].length;


for (int i=0; i< filas; i++){
for(int j=0; j <columnas;j++){
if (mat [i][j]==1){
for (int h=1; h< filas-i; h++){
if (mat[i+h][j]==1 && mat[i][j+h]==1 && mat[i+h][j+h]==1) {
return true;
}


}
}

}

}

return false;
}
}


Creo que la logica esta bien, pero por algun motivo no me valida los casos.

Gracias por su ayuda!
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 Kabuto
Val: 3.428
Oro
Ha mantenido su posición en Java (en relación al último mes)
Gráfica de Java

Que esta fallando?

Publicado por Kabuto (1385 intervenciones) el 14/09/2022 19:02:46
Humm.. interesante.

He hecho yo mi propio intento sin ver tú código, y luego me he dado cuenta que he acabado aplicando tu misma lógica. Un poco diferente, usando un método recursivo en lugar de un bucle y controlando con TRY CATCH el (inevitable) momento en que me salgo de los límites de la matriz.

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
import java.util.Arrays;
 
public class CuadradoEnMatriz {
 
	public static void main(String[] args) {
 
		int[][] matriz = {
				{0,0,1,1,0},
				{0,0,1,1,0},
				{0,0,0,0,0}
		};
 
		System.out.println("Matriz de números");
		for (int[] linea: matriz)
			System.out.println(Arrays.toString(linea));
 
		System.out.println(hayCuadrado(matriz)?"\nSí hay cuadrado":"\nNo hay cuadrado");
 
	}
 
	private static boolean hayCuadrado(int[][] mat) {
		for (int x = 0; x < mat.length; x++)
			for (int y = 0; y < mat[x].length; y++) {
				if (mat[x][y] == 1) {
					if (compruebaArea(mat, x, y, 1)) //Comenzamos a buscar con un area de valor 1
						return true; //El método recursivo ha ampliado el area de búsqueda hasta encontrar un cuadrado
				}
				//Si método recursivo no encuentra cuadrado, no hacemos nada. Los bucles continuan buscando otro 1
			}
 
		//Bucles han terminado de recorrer matriz sin encontrar cuadrado.
		return false;
	}
 
	private static boolean compruebaArea(int[][] mat, int x, int y, int area) {
		try {
			//System.out.printf("\n%d,%d,%d",mat[x][y+area],mat[x+area][y],mat[x+area][y+area]);
			if (mat[x][y+area] == 1 && mat[x+area][y] == 1 && mat[x+area][y+area] == 1)
				return true; //Se ha encontrado un area que forma un cuadrado
			else
				//No se ha encontrado un cuadrado
				return compruebaArea(mat, x, y, ++area);//Intentamos con un área más amplia
		}
		catch(IndexOutOfBoundsException ex) {
			//Nos hemos salido de los limites de la matriz.
			//No hay un area de cuadrado desde las coordenadas actuales
			return false;
		}
	}
 
}

E iba convencido de que iba a funcionar, pero no.
Y ya me he dado cuenta de cuál es NUESTRO problema.
Y es que usando esta lógica, solo podemos encontrar cuadriláteros regulares, es decir, cuadrados que tengan la misma base y la misma altura.
Nuestros códigos sí encuentran este cuadrado:
1
2
3
4
5
6
Matriz de números
[0, 0, 1, 1, 0]
[0, 0, 1, 1, 0]
[0, 0, 0, 0, 0]
 
Sí hay cuadrado

O este:
1
2
3
4
5
6
Matriz de números
[0, 0, 1, 0, 1]
[0, 0, 0, 0, 0]
[0, 0, 1, 0, 1]
 
Sí hay cuadrado

Pero no este:
1
2
3
4
5
6
Matriz de números
[0, 0, 1, 0, 1]
[0, 0, 1, 0, 1]
[0, 0, 0, 0, 0]
 
No hay cuadrado
Los dos primeros sí porque sus vértices (los 1) están todos a la misma distancia entre ellos.
En este tercer caso, no están a la misma distancia

Y una cosa te digo, es que en realidad eso NO es un cuadrado, es un RECTÁNGULO.
Así que podemos estar orgullosos de nuestra lógica je je...

Pero..., el enunciado dice que debemos considerarlo como una entrada válida.
Así que debemos pensar en una nueva lógica.... a ver qué se me ocurre y te cuento xD

Un saludo.
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
Imágen de perfil de Kabuto
Val: 3.428
Oro
Ha mantenido su posición en Java (en relación al último mes)
Gráfica de Java

Que esta fallando?

Publicado por Kabuto (1385 intervenciones) el 14/09/2022 20:12:54
Vale.
Creo que he dado con una solución.
No es tan elegante como la anterior, y no se si tal vez exista una forma más sencilla de resolverlo. Pero yo solo he podido dar con esta.

Lo que hago es, cuando encuentro un 1, hago un barrido horizontal desde esa posición y busco más 1's. Y anoto en un array las distancias a la que se encuentran respecto al 1 que consideramos como "origen"
Luego hago lo mismo, pero en vertical.

Así, tengo una lista de distancias horizontales y verticales donde he encontrado distintos 1's respecto al "origen". Pues aplicando esas distancias a las coordenadas del "origen" compruebo si encuentro el cuarto 1 que me faltaría para cerrar el cuadrado, o rectángulo...
Si lo encuentro, pues genial, retorno TRUE.

Si no lo encuentro, pues el proceso sigue buscando otro 1 que sirva de "origen", para el cuál volveremos a crear nuevas "listas de distancias" horizontales y verticales con las que buscar el cuarto 1 que nos falta.

Cuando ya no queden 1's que sirvan de origen, pues se acabó, no hay cuadrado. Retorno FALSE.

Es un poco complicado de explicar..., pero en realidad es el mismo proceso que hacemos (al menos hago yo) mentalmente cuando miro la matriz y decido si estoy viendo un cuadrado o no.

El código que he escrito, quizás se podría haber simplificado un poco más si se pudiera usar un ArrayList para hacer las "listas de distancias" o incluso si se pudiera usar POO y modelar alguna clase.
Pero no parece que sea el caso.

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
public class CuadradoEnMatriz {
 
	public static void main(String[] args) {
 
		int[][] matriz = {
				{1,0,1,0,1},
				{1,0,0,0,0},
				{0,1,1,0,1}
		};
 
		System.out.println("Matriz de números");
		for (int[] linea: matriz)
			System.out.println(Arrays.toString(linea));
 
		System.out.println(hayCuadrado(matriz)?"\nSí hay cuadrado":"\nNo hay cuadrado");
 
	}
 
	private static boolean hayCuadrado(int[][] mat) {
		for (int x = 0; x < mat.length; x++)
			for (int y = 0; y < mat[x].length; y++)
				if (mat[x][y] == 1) {
					/*
					 * Hemos encontrado un 1 que podría ser "origen" de un cuadrado.
					 * Vamos a buscar otros 1 en su horizontal y su vertical
					 * y anotaremos a que distancia se encuentran cada uno de ellos
					 * Comprobaremos si con esas distancias, podemos conformar un cuadrado
					 */
					int[] horizontal = getDistanciasHorizontal(mat, x, y);
					int[] vertical = getDistanciasVertical(mat, x, y);
 
					//Si hemos encontrado 1 en ambos sentidos...
					if (horizontal != null && vertical != null) {
						/*
						 * Ahora comprobamos si con estas distancias,
						 * al aplicarlas en la horizontal y en la vertical
						 * encontramos otro 1 que permita cerrar un cuadrado.
						 */
						//El límite de comprobaciones, depende del array más pequeño
						int tope = 0;
						if (horizontal.length < vertical.length)
							tope = horizontal.length;
						else
							tope = vertical.length;
						for (int i = 0; i < tope; i++) {
							if (mat[x + vertical[i]][y + horizontal[i]] == 1)
								return true; //Se ha encontrado un 1 que cierra un cuadrado
						}
						//Bucle FOR no ha encontrado un 1 que cierre cuadrado.
						//El método continuará buscando otro nuevo 1 desde el que calcular nuevas distancias.
					}
				}
		//Ningún 1 encontrado ha podido cerrar un cuadrado.
		return false;
	}
 
	private static int[] getDistanciasHorizontal(int[][] mat, int x, int y) {
		//Dos recorridos.
		//Primero, para contar cuantos 1 hay en esta horizontal
		int cant = 0;
		for (int h = y+1; h < mat[x].length; h++) {
			if (mat[x][h] == 1)
				cant++;
		}
		if (cant == 0)
			return null; //No hay ningun 1
		else {
			//Segundo recorrido, esta vez para crear un array con las distancias donde se encuentran los 1
			int[] dist = new int[cant];
			int d = 0;
			for (int h = y+1; h < mat[x].length; h++) {
				if (mat[x][h] == 1) {
					dist[d] = h - y; //Anotamos distancia
					d++; //Incrementamos indice del array de distancias
				}
			}
			//Recorrido terminado, retornamos distancias
			return dist;
		}
	}
 
	private static int[] getDistanciasVertical(int[][] mat, int x, int y) {
		//Dos recorridos.
		//Primero, para contar cuantos 1 hay en esta vertical
		int cant = 0;
		for (int v = x+1; v < mat.length; v++) {
			if (mat[v][y] == 1)
				cant++;
		}
		if (cant == 0)
			return null; //No hay ningun 1
		else {
			//Segundo recorrido, esta vez para crear un array con las distancias donde se encuentran los 1
			int[] dist = new int[cant];
			int d = 0;
			for (int v = x+1; v < mat.length; v++) {
				if (mat[v][y] == 1) {
					dist[d] = v - x; //Anotamos distancia
					d++; //Incrementamos indice del array de distancias
				}
			}
			//Recorrido terminado, retornamos distancias
			return dist;
		}
	}

Si lo probamos, detecta cuadrados:
1
2
3
4
5
6
Matriz de números
[1, 0, 1, 0, 1]
[1, 0, 0, 0, 0]
[0, 1, 1, 0, 1]
 
Sí hay cuadrado

Y también rectángulos:
1
2
3
4
5
6
Matriz de números
[1, 0, 1, 0, 1]
[0, 0, 1, 0, 1]
[0, 1, 0, 0, 0]
 
Sí hay cuadrado

Solo da por buenos cuadrados y rectángulos, que son los que tienen todos sus angulos de 90º
El resto de cuadriláteros, no son aceptables.
1
2
3
4
5
6
Matriz de números
[0, 0, 1, 0, 1]
[0, 0, 1, 0, 0]
[0, 0, 0, 0, 1]
 
No hay cuadrado


Espero que puedas entender la lógica que he aplicado.
Pregunta lo que necesites.
Un saludo.
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