Рубрики

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

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

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

// C / C ++ код для квадрата максимального размера
// подматрица со всеми 1
#include <stdio.h>
#define bool int
#define R 6
#define C 5

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для получения минимум трех значений * /

int min(int a, int b, int c)

{

    int m = a;

    if (m > b)

        m = b;

    if (m > c)

        m = c;

    return m;

}

  

void printMaxSubSquare(bool M[R][C])

{

    int i, j;

    int S[R][C];

    int max_of_s, max_i, max_j;

  

    / * Установить первый столбец S [] [] * /

    for (i = 0; i < R; i++)

        S[i][0] = M[i][0];

  

    / * Установить первый ряд S [] [] * /

    for (j = 0; j < C; j++)

        S[0][j] = M[0][j];

  

    / * Построить другие записи S [] [] * /

    for (i = 1; i < R; i++) {

        for (j = 1; j < C; j++) {

            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 = 0; i < R; i++) {

        for (j = 0; j < C; j++) {

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

                max_of_s = S[i][j];

                max_i = i;

                max_j = j;

            }

        }

    }

  

    printf("Maximum size sub-matrix is: \n");

    for (i = max_i; i > max_i - max_of_s; i--) {

        for (j = max_j; j > max_j - max_of_s; j--) {

            printf("%d ", M[i][j]);

        }

        printf("\n");

    }

}

  

  

  
/ * Функция драйвера для проверки вышеуказанных функций * /

int main()

{

    bool M[R][C] = { { 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);

    getchar();

}

Выход:

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

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

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

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

0.00 (0%) 0 votes