Найти число '+', образованное всеми единицами в двоичной матрице

Question

Вопрос, который у меня возник, похож на проблему, найденную здесь: https://www.geeksforgeeks.org/find-size-of-the-largest-formed-by-all-ones-in-a-binary-matrix/

Разница в том, что '+' должно иметь все остальные ячейки в матрице, чтобы быть нулями.Например:

00100  
00100   
11111   
00100   
00100

Это будет матрица 5x5 с 2 '+', одна внутри другой.

Другой пример:

00010000  
00010000  
00010000  
11111111  
00010000  
00010010
00010111
00010010

Эта матрица имеет размер 8x8 и будет иметь 3 '+', одна из которых - маленькая матрица 3x3 в правом нижнем углу, а другая 2 сформированаиз матрицы 5x5, одна внутри другой, аналогично первому примеру.

Используя код по ссылке выше, я могу получить только пока:

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)

В настоящее время он возвращаетвывод самой длинной стороны знака «+».Желаемым выводом будет число «+» в квадратной матрице.

У меня возникают проблемы с проверкой всех остальных ячеек в матрице на нули и нахождением отдельного «+», если он есть ввся матрица.

Любая помощь с благодарностью.

Answer 1

Я не хочу испортить удовольствие от решения этой проблемы, поэтому вместо решения вот несколько советов:

1. Попробуйте написать подпрограмму (функцию), котораяучитывая квадратную матрицу в качестве входного, решает, является ли эта входная матрица «+» или нет (скажем, функция возвращает «1», если это «+» и «0» в противном случае).
2. Изменитьфункция из 1. так что вы можете дать ей в качестве входных данных подматрицу полной матрицы (в которой вы хотите сосчитать '+').Более конкретно, вводом может быть координата левого верхнего элемента подматрицы и его размер.Возвращаемое значение должно быть таким же, как и для 1.
3. Можете ли вы написать цикл, который проверяет все подматрицы вашей заданной матрицы и подсчитывает те, которые '+', используя функцию из 2.?

Вот несколько незначительных замечаний: Алгоритм, к которому это приводит, запускается за полиномиальное время (в измерении входной матрицы), поэтому в основном он не должен занимать много времени.Я не слишком много думал об этом, но, возможно, алгоритм можно сделать более эффективным.Кроме того, вам следует подумать о том, считаете ли вы «1», заключенный в «0», как «+» или нет.