Nombre de submatrius quadrades constants X22897
Cada cas d’entrada d’aquest exercici és una matriu de 0s i 1s. El programa ha de calcular el nombre total de submatrius no-buides, quadrades i constants (amb tantes files com columnes i amb el mateix símbol). Per exemple, considereu aquesta matriu d’entrada:
00001 00011 00011 01111
Té 1 submatriu 3×3 constant (amb 0s), té 6 submatrius 2×2 constants (4 d’elles amb 0s, i 2 d’elles amb 1s), i té 20 submatrius 1×1 constants. Per tant, en aquest cas la sortida serà 27.
Entrada
L’entrada té varis casos. Cada cas comença amb dos naturals positius n,m en una primera línia. Després venen n línies amb m caràcters 0 o 1, que descriuen una matriu n×m de 0s i 1s. Després ve una línia en blanc.
Sortida
Per a cada cas, el programa ha d’escriure el nombre total de submatrius no buides i constants en una línia.
Observació
Avaluació sobre 10 punts:
- Solució lenta: 5 punts.
- Solució ràpida: 10 punts.
Entenem com a solució ràpida una que és correcta, de cost lineal i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.
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