Number of constant square submatrices X22897
Each case of the input in this exercise is a matrix of 0s and 1s. The program has to compute the total number of non-empty submatrices that are square and constant (same number of rows and columns and the same symbol). For instance, consider this as the input matrix:
00001 00011 00011 01111
It has 1 constant submatrix of size 3×3 (with 0s), 6 constant submatrices 2×2 (4 of them with 0s, and 2 of them with 1s), and 20 constant submatrices 1×1. Therefore, in this case the output would be 27.
Input
The input has several cases. Each case starts with a line with two positive naturals n and m. After that come n lines with m characters, either 0 or 1, which describe a matrix of size n×m, followed by an empty line.
Output
For each case, the program must write the total number of non-empty square submatrices in one line.
Observation
Evaluation out of 10 points:
- Slow solution: 5 points.
- Fast solution: 10 points.
A fast solution is one which is correct, of linear cost and passing the test cases, both public and private. A slow solution is one which is not fast, but it is correct and passes the public test cases.
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