Número de submatrices cuadradas constantes X22897
Cada caso de entrada de este ejercicio es una matriz de 0s y 1s. El programa debe calcular el número total de submatrizes no-vacías, cuadradas y constantes (con tantas filas como columnas i con el mismo símbolo). Por ejemplo, considerad esta matriz de entrada:
00001 00011 00011 01111
Tiene 1 submatriz 3×3 constante (con 0s), 6 submatrices 2×2 constantes (4 de ellas con 0s, i 2 de ellas con 1s), y 20 submatrices 1×1 constantes. Por tanto, en este caso la salida será 27.
Entrada
La entrada tiene varios casos. Cada caso comienza con dos naturales positivos n y m en una primera línea. Después vienen n líneas con m caracteres 0 y 1, que describen una matriz n×m de 0s i 1s, seguidas de una línea en blanco.
Salida
Para cada caso, el programa debe escribir el número total de submatrices no vacías y constantes en una línea.
Observación
Evaluación sobre 10 puntos:
- Solución lenta: 5 puntos.
- Solución rápida: 10 puntos.
Entendemos por solución rápida una que es correcta, de coste lineal y capaz de superar los juegos de prueba públicos y privados. Entendemos una solución lenta una que no es rápida, pero es correcta y capaz de superar los juegos de prueba públicos.
Input
4 7 1011111 1101111 1111111 1010110 10 4 0010 1000 1011 0000 0000 0000 0000 0101 0000 0000 10 3 000 000 100 100 000 000 010 010 001 001 8 9 000000000 100000000 000000000 000100001 100010100 010000000 000001000 000000000 7 6 100100 000000 001000 101000 010000 000000 000000 1 8 10110001 3 1 1 1 0 7 5 11011 10111 11111 11001 01111 11111 10111 2 1 0 1 10 5 11110 01011 11111 11111 11111 11111 11111 10101 11111 11011 7 6 000000 000001 000000 001010 100100 000010 000000 6 1 0 1 0 1 1 1 2 6 100111 111111 5 5 00000 00000 11000 01000 01000 8 9 111111111 110110110 111111111 111111010 111011111 111011111 111111111 111011111 5 4 1111 0111 1111 0101 1101 10 8 10111111 11111111 11111101 11011101 11111111 11110111 11110011 11111111 11111111 11010111 5 8 11110101 01111111 11110111 11101111 11111110 2 1 1 0 1 9 100011110
Output
38 57 38 115 64 8 3 45 2 83 58 6 14 38 116 25 132 57 2 9