Рубрики

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

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

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

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

  

using System;

  

public class GFG {

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

    static void printMaxSubSquare(int[, ] M)

    {

        int i, j;

        // нет строк в M [,]

        int R = M.GetLength(0);

        // нет столбцов в M [,]

        int C = M.GetLength(1);

        int[, ] S = new int[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] = Math.Min(S[i, j - 1],

                                       Math.Min(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;

                }

            }

        }

  

        Console.WriteLine("Maximum size sub-matrix is: ");

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

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

                Console.Write(M[i, j] + " ");

            }

            Console.WriteLine();

        }

    }

  

    // Драйвер программы

    public static void Main()

    {

        int[, ] M = new int[6, 5] { { 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);

    }

}

Выход:

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

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

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

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

0.00 (0%) 0 votes