Programacion, ACM ICPC, UVa Online Judge

El link del problema es el siguiente:
11110 – Equidivisions

Lo que nos piden es determinar si dada una descripción de una matriz, hay que decir si hay “n” conjuntos de “n” elementos en total.
La primera linea nos dice el numero de conjuntos que habrá, haré mención a esta variable como n, seguido de n-1 renglones.

Cada renglon indica las posicion de los elementos pertenecientes al conjunto 1,2,3,…,n-1.
Los elementos sobrantes en la matriz son los elementos que pertenecen al conjunto n.
Ejemplo:

5
1 1 1 2 1 3 3 2 2 2
2 1 4 2 4 1 5 1 3 1
4 5 5 2 5 3 5 5 5 4
2 5 3 4 3 5 4 3 4 4

Tomamos solo el primer renglon:
1 1 1 2 1 3 3 2 2 2
Aca hay que verlo como parejas que vendrian siendo las siguientes:
1 1
1 2
1 3
3 2
2 2
Esas parejas representan las coordenadas de los elementos en el conjunto 1.
Como se observa son 5 conjuntos pero solo nos dan 4 renglones, debido a que los elementos sobrantes en la matriz, representan al ultimo conjunto.

El primer paso es obtener cuantos elementos tiene cada conjunto
Por ejemplo si nos dan lo siguiente como entrada:
5
1 1 1 2
2 2
3 3
4 4
Podemos decir que esta mal, ya que el primer conjunto tiene 2 elementos y los demás 1 elemento, ademas que el ultimo conjunto tiene mas de 2 elementos.
Si la entrada no pasa la primera validación, podemos imprimir un “wrong”.
Una vez validado que en la entrada todos los conjuntos tienen el mismo numero de elementos, hay que revisar que estén conectados.

Para la conectividad el problema especifica que es en 4 adyacencias (arriba,abajo,izquierda,derecha).
Lo que hacemos es recorrer la matriz y cada vez que encontremos un elemento que no hemos analizado, realizar un flood fill.
Cuando digo elemento, me refiero a cada posición de la matriz individualmente.
Ejemplo:

5
1 1 1 2 1 3 3 2 2 2
2 1 3 1 4 1 5 1 4 2
4 5 5 2 5 3 5 5 5 4
2 4 1 4 3 5 4 3 4 4

Esa entrada pertenece a la segunda imagen mostrada en el problema.
Una vez procesada la entrada y vemos que la validación es correcta, procedemos a revisar la conectividad.
Primero procederiamos a analizar el conjunto de unos, que no tiene problemas.
Después a analizar el conjunto de los cuatro, que solo marcaría los números 4 que se encuentran adyacentes, el de la posición 1,4 y 2,4.
Luego a analizar el conjunto del numero cinco, que marcara solo los números en la posición 1,5 y 2,5.
Luego a analizar el conjunto del numero dos, que no tiene problemas.
Luego a analizar el otro conjunto del numero 5, ya que estos no se contaron al analizar al primer conjunto encontrado.
Acá, al ver que analizamos un conjunto que ya estaba analizado, podríamos terminar el algoritmo y decir “wrong”.

Si al terminar de realizar el flood fill sobre todos los conjuntos, tenemos que no analizamos nuevamente un conjunto, entonces la matriz dada es correcta.

Código en C++

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: