Find number of ‘+’ formed by all ones in a binary matrix

Question

The question I have is similar to the problem found here: https://www.geeksforgeeks.org/find-size-of-the-largest-formed-by-all-ones-in-a-binary-matrix/

The difference is the '+' must have all other cells in the matrix to be zeros. For example:

00100  
00100   
11111   
00100   
00100

This will be a 5x5 matrix with 2 '+', one inside another.

Another example:

00010000  
00010000  
00010000  
11111111  
00010000  
00010010
00010111
00010010

This matrix is 8x8, and will have 3 '+', one of it is the small 3x3 matrix in the bottom right, and the other 2 is formed from the 5x5 matrix, one inside another, similar to the first example.

Using the code from the link above, I can only get so far:

M = [[0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0],
     [0, 0, 0, 1, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1],
     [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 1, 0],
     [0, 0, 0, 1, 0, 1, 1, 1], [0, 0, 0, 1, 0, 0, 1, 0]]
R = len(M)
N = len(M)
C = len(M[0])
left = [[0 for k in range(C)] for l in range(R)]
right = [[0 for k in range(C)] for l in range(R)]
top = [[0 for k in range(C)] for l in range(R)]
bottom = [[0 for k in range(C)] for l in range(R)]
for i in range(R):
    top[0][i] = M[0][i]
    bottom[N - 1][i] = M[N - 1][i]
    left[i][0] = M[i][0]
    right[i][N - 1] = M[i][N - 1]
for i in range(R):
    for j in range(1,R):
        if M[i][j] == 1:
            left[i][j] = left[i][j - 1] + 1
        else:
            left[i][j] = 1
        if (M[j][i] == 1):
            top[j][i] = top[j - 1][i] + 1
        else:
            top[j][i] = 0
        j = N - 1 - j
        if (M[j][i] == 1):
            bottom[j][i] = bottom[j + 1][i] + 1
        else:
            bottom[j][i] = 0
        if (M[i][j] == 1):
            right[i][j] = right[i][j + 1] + 1
        else:
            right[i][j] = 0
        j = N - 1 - j
n = 0
for i in range(N):
    for j in range(N):
        length = min(top[i][j], bottom[i][j], left[i][j], right[i][j])
        if length > n:
            n = length
print(n)

Currently, it returns the output of the longest side of the '+'. The desired output would be the number of '+' in the square matrix.

I am having trouble checking for all other cells in the matrix to be zeros, and finding a separate '+' if there is one in the entire matrix.

Any help is greatly appreciated.

Answer 1

I don't want to spoil the fun of solving this problem, so rather than a solution, here are some hints:

1. Try to write a sub-routine (a function), that given a square matrix as input, decides whether this input matrix is a '+' or not (say the function returns a '1' if it is a '+' and a '0' otherwise).
2. Modify the function from 1. so that you can give it as input a submatrix of the full matrix (in which you want to count '+'). More specifically, the input could be the coordinate of the upper left entry of the submatrix and its size. The return value should be the same as for 1.
3. Can you write a loop that examines all the submatrices of your given matrix and counts the ones that are '+' using the function from 2.?

Here are some minor remarks: The algorithm that this leads to runs in polynomial time (in the dimension of the input matrix), so basically it shouldn't take to long. I haven't thought about it too much, but probably the algorithm can be made more efficient. Also, you should maybe think about whether or not you count a '1' that is surrounded by '0's as a '+' or not.