Enunciado original
No viene mal comenzar el concurso ganando un poco de confianza, así que bienvenido sea un problema fácil. Un primer paso en el apasionante campo del reconocimiento de formas que a su vez entra en el mundo de la visión artificial.
Traduciendo el enunciado: vamos a tener una cuadrícula con cuadros blancos y negros. Se trata de decir si todos los cuadros negros forman un cuadrado relleno.
El tamaño del tablero máximo que nos proponen (20x20) es suficientemente pequeño como para almacenarlo por completo en memoria así que, en principio, lo más sencillo parece tener este tablero en memoria para trabajar con él.
Vamos a comenzar con una versión previa que lea los datos y los guarde en memoria. Nos quedaría algo así:
#include <iostream>
int main()
{
bool tabla[21][21]; // Fila-columna adicional para no comprobar bordes
int T,n,i,j;
char buffer[21];
std::cin >> T;
for (int t=1; t<=T; t++) // casos
{
int nsq=0; // n. pixels black
std::cin >> n; // input
for (i=0; i<n; i++)
{
std::cin >> buffer;
for (j=0; j<n; j++)
{
tabla[i][j]=(buffer[j]=='#');
if (tabla[i][j]) nsq++;
}
tabla[i][n]=false;
}
for (j=0; j<=n; j++)
tabla[n][j]=false;
bool result=false;
std::cout << "Case #" << t << ": " << (result ? "YES" : "NO") << std::endl;
}
return 0;
}
Necesitamos las librerías de entradas/salidas basadas en los streams de C++, así que cargamos sus definiciones con la instrucción include.
Para almacenar las casillas de la cuadrícula he elegido un array de dos dimensiones de valores bool puesto que cada casilla puede tener dos valores (blanco o negro) que asimilaremos por false o true. He asignado una fila y una columna adicional en la cuadrícula (21x21 en lugar de 20x20) para simplificar el algoritmo, pero esto lo explicaré más adelante.
El primer dato que vendrá es el número de casos a analizar, así que lo leemos en la variable T y escribimos un bucle que se repita para cada caso.
Dentro de ese bucle leemos los datos de cada caso. El primer dato que nos vendrá va a ser la dimensión de la cuadrícula, la almacenamos en la variable n. Luego n filas de n caracteres con los cuadros blancos y negros. Los leemos en un bucle controlado por la variable i.
Leeremos cada fila de una vez en el array buffer, dimensionado para poder almacenar los 20 caracteres que como máximo formarán la fila más uno adicional para el carácter especial 0x00 de fin de cadena. Convertimos la secuencia de caracteres leída en los valores bool que guardamos en el array tabla en un bucle anidado controlado por la variable j y vamos dando el valor true a las casillas ocupadas por un pixel negro. Al final de cada fila agregamos un pixel adicional a valor false (blanco) y después de leer la última fila colocamos una fila adicional de pixels blancos.
Además, al principio del primer bucle asignamos el valor cero a la variable nsq. Cada vez que almacenemos un valor true en tabla incrementaremos esta variable nsq con lo que al final en ella tendremos el número de pixels negros de la cuadrícula.
Terminamos el bucle con lo que será el principio y el final del algoritmo de los casos. El principio: definimos una variable de tipo bool en la que calcularemos el resultado del algoritmo (true si los pixels forman un cuadrado, false en caso contrario). El final: el fichero de salida donde convertimos el valor bool de result a los textos YES o NO como nos especifican.
El algoritmo para saber si todos los pixels negros forman un cuadrado es muy sencillo: hay que localizar el primero y a partir de ese comprobar que horizontal y verticalmente todos los pixels negros estén juntos, la longitud horizontal y vertical sea la misma y no haya pixels negros fuera de esta zona.
Localizar el primer pixel negro se reduce a ir comprobando los valores de tabla por filas hasta encontrar el primer valor true. Necesitaremos dos bucles anidados, así:
int x,y;
for (i=0; !result && (i<n); i++) // localizar esquina
for (j=0; !result && (j<n); j++)
{
result=tabla[i][j];
if (result)
{
x=i; y=j;
}
}
En el momento que encontremos el primer pixel negro colocaremos true en la variable result que como está incluida en las condiciones de finalización del bucle hará que se terminen los bucles anidados. Guardamos en las variables x e y la localización de la esquina del supuesto cuadrado.
A partir de esta esquina podríamos ir avanzando hacia el final de la fila para ir contando pixels negros consecutivos. Con el primer pixel blanco terminaríamos la búsqueda y ya sabríamos el número de pixels que tendría el lado del supuesto cuadrado.
Sin embargo, pensando un poco, ya sabemos qué lado tiene que tener el supuesto cuadrado. Para eso hemos contado los pixels negros que tenía nuestra cadrícula. Si todos los pixels negros forman un cuadrado, éste tendrá de lado la raíz cuadrada del número de pixels. Geometría elemental.
Necesitaremos incluir la cabecera de la librería que contiene las funciones matemáticas:
#include <math.h>
Y entonces, al comienzo del algoritmo calcularemos directamente el lado esperado:
int lado=sqrt(nsq); // lado esperado del cuadrado
Donde sqrt es la función que devuelve la raíz cuadrada de un número. Si el número de pixels no es un cuadrado perfecto ya es imposible que formen un cuadrado por lo que sería una buena idea antes de comenzar ningún bucle comparar esto. Encerramos los bucles de antes (y los que haremos a continuación para comprobar que todos los pixels están formando un cuadrado) en la siguiente comparación:
if ((lado>0) && ((lado*lado)==nsq)) // num pixels correctos
{
}
Sabiendo el lado y que el número de pixels puede ser correcto y teniendo localizada la esquina del supuesto cuadrado sólo queda, con otros dos bucles anidados, muy similares a los primeros, que todos los pixels que forman el hipotético cuadrado son negros:
for (i=0; result && (i<lado); i++) // comprobar relleno
for (j=0; result && (j<lado); j++)
result=tabla[i+x][j+y];
Asignamos los valores del array tabla a la derecha y hacia abajo una distancia de lado a partir del punto (x,y) a la variable result. Como antes, en cuanto se asigne el valor false los bucles terminarán. Para que el cuadrado sea perfecto deben terminarse todas las iteraciones sin que esto ocurra.
Y eso es todo el algoritmo. ¿Pero por qué no he comprobado en ningún momento que no me salía de la cuadrícula? Pues gracias a que he añadido esa falsa fila y columna a mi cuadrícula con todos los valores a false. En el momento que la comparación alcanzara estas casillas, que quedan fuera de la cuadrícula real, el valor va a ser false y terminará el bucle. Siempre que tengo tableros intento usar esta estrategia para eliminar un montón de comparaciones con los bordes del tablero.
Este es el programa completo y aquí el fichero de entrada del concurso.
Esta fue mi implementación, pero ¿podría haberse hecho sin usar el array tabla?. La respuesta es sí. Pensad un poco sobre cómo...
¿Una ayuda? Si tenemos contados los pixels negros y pueden formar un cuadrado y hemos calculado su lado nos basta con sacar las coordenadas mínima y máxima horizontal y vertical de todos los pixels negros. La diferencia entre la máxima y la mínima horizontal y vertical tiene que ser lado-1 para que formen un cuadrado. Así que nos sobra con definir cuatro variables int e ir comparando las coordenadas de los pixels negros que vayamos leyendo para localizar los valores extremos, sobrándonos el array tabla.
Siempre suele haber un algoritmo mejor que el nuestro... lo importante es que el nuestro funcione suficientemente bien.
