Рубрики

Программа Python для квадратной подматрицы максимального размера со всеми единицами

По заданной двоичной матрице определите квадратную подматрицу максимального размера со всеми единицами.

Например, рассмотрим приведенную ниже двоичную матрицу.

# Python3 код для максимального размера
# квадратная подматрица со всеми 1

  

def printMaxSubSquare(M):

    R = len(M) № № строк в M [] []

    C = len(M[0]) № № столбцов в M [] []

  

    S = [[0 for k in range(C)] for l in range(R)]

    # здесь мы установили первую строку и столбец S [] []

  

    # Построить другие записи

    for i in range(1, R):

        for j in range(1, C):

            if (M[i][j] == 1):

                S[i][j] = min(S[i][j-1], S[i-1][j],

                            S[i-1][j-1]) + 1

            else:

                S[i][j] = 0

      

    # Найти максимальную запись и

    # индексы максимальной записи в S [] []

    max_of_s = S[0][0]

    max_i = 0

    max_j = 0

    for i in range(R):

        for j in range(C):

            if (max_of_s < S[i][j]):

                max_of_s = S[i][j]

                max_i = i

                max_j = j

  

    print("Maximum size sub-matrix is: ")

    for i in range(max_i, max_i - max_of_s, -1):

        for j in range(max_j, max_j - max_of_s, -1):

            print (M[i][j], end = " ")

        print("")

  
# Драйверная программа

M = [[0, 1, 1, 0, 1],

    [1, 1, 0, 1, 0],

    [0, 1, 1, 1, 0],

    [1, 1, 1, 1, 0],

    [1, 1, 1, 1, 1],

    [0, 0, 0, 0, 0]]

  
printMaxSubSquare(M)

  
# Этот код предоставлен Soumen Ghosh

Выход:

Maximum size sub-matrix is: 
1 1 1 
1 1 1 
1 1 1

Пожалуйста, обратитесь к полной статье о максимальном размере квадратной подматрицы со всеми 1 для получения более подробной информации!

Рекомендуемые посты:

Программа Python для квадратной подматрицы максимального размера со всеми единицами

0.00 (0%) 0 votes