Рубрики

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

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

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

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

public class GFG {

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

    static void printMaxSubSquare(int M[][])

    {

        int i, j;

        int R = M.length; // нет строк в M [] []

        int C = M[0].length; // нет столбцов в M [] []

        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;

                }

            }

        }

  

        System.out.println("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--) {

                System.out.print(M[i][j] + " ");

            }

            System.out.println();

        }

    }

  

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

    public static void main(String[] args)

    {

        int 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);

    }

}

Выход:

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

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

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

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

0.00 (0%) 0 votes