Рубрики

Учитывая матрицу 'O' и 'X', найдите самый большой квадрат, окруженный 'X'

Учитывая матрицу, в которой каждый элемент является либо «O», либо «X», найдите наибольшую субквадрату, окруженную «X».

В статье ниже предполагается, что данная матрица также является квадратной матрицей. Код, приведенный ниже, может быть легко расширен для прямоугольных матриц.

Примеры:

Input: mat[N][N] = { {'X', 'O', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'O', 'X', 'O'},
                     {'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'O'},
                    };
Output: 3
The square submatrix starting at (1, 1) is the largest
submatrix surrounded by 'X'

Input: mat[M][N] = { {'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'O', 'X', 'X', 'O', 'X'},
                     {'X', 'X', 'X', 'O', 'O', 'X'},
                     {'X', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'O'},
                    };
Output: 4
The square submatrix starting at (0, 2) is the largest
submatrix surrounded by 'X'

Простое решение — рассмотреть каждую квадратную подматрицу и проверить, все ли угловые ребра заполнены знаком «X». Временная сложность этого решения составляет O (N 4 ).

Мы можем решить эту проблему за O (N 3 ) времени, используя дополнительное пространство. Идея состоит в том, чтобы создать два вспомогательных массива hor [N] [N] и ver [N] [N]. Значение, хранимое в hor [i] [j], представляет собой количество горизонтальных непрерывных символов «X» до mat [i] [j] в mat [] []. Аналогично, значение, хранящееся в ver [i] [j], представляет собой число непрерывных вертикальных символов «X» до mat [i] [j] в mat [] []. Ниже приведен пример.


mat[6][6] =  X  O  X  X  X  X
             X  O  X  X  O  X
             X  X  X  O  O  X
             O  X  X  X  X  X
             X  X  X  O  X  O
             O  O  X  O  O  O

hor[6][6] = 1  0  1  2  3  4
            1  0  1  2  0  1
            1  2  3  0  0  1
            0  1  2  3  4  5
            1  2  3  0  1  0
            0  0  1  0  0  0

ver[6][6] = 1  0  1  1  1  1
            2  0  2  2  0  2
            3  1  3  0  0  3
            0  2  4  1  1  4
            1  3  5  0  2  0
            0  0  6  0  0  0

После того, как мы заполнили значения в hor [] [] и ver [] [], мы начинаем с самого нижнего правого угла матрицы и двигаемся по направлению к крайнему левому верхнему углу строки за строкой. Для каждого посещенного входа mat [i] [j] мы сравниваем значения hor [i] [j] и ver [i] [j] и выбираем меньшее из двух, когда нам нужен квадрат. Пусть меньшее из двух будет «маленьким». Выбрав меньшее из двух, мы проверяем, есть ли ver [] [] и hor [] [] для левого и верхнего ребер соответственно. Если у них есть записи для того же самого, то мы нашли подквадрату. В противном случае мы стараемся для малого-1.

Ниже приведена реализация вышеуказанной идеи.

C ++

// Программа на C ++ для поиска наибольшего квадрата
// окружены 'X' в заданной матрице 'O' и 'X'
#include<iostream>

using namespace std;

  
// Размер данной матрицы равен NXN
#define N 6

  
// Полезная функция для поиска минимум двух чисел

int getMin(int x, int y) { return (x<y)? x: y; }

  
// Возвращает размер матрицы максимального размера
// в окружении 'X'

int findSubSquare(int mat[][N])

{

    int max = 0; // Инициализировать результат

  

    // Инициализируем левое верхнее значение в hor [] [] и ver [] []

    int hor[N][N], ver[N][N];

    hor[0][0] = ver[0][0] = (mat[0][0] == 'X');

  

    // Заполняем значения в hor [] [] и ver [] []

    for (int i=0; i<N; i++)

    {

        for (int j=0; j<N; j++)

        {

            if (mat[i][j] == 'O')

                ver[i][j] = hor[i][j] = 0;

            else

            {

                hor[i][j] = (j==0)? 1: hor[i][j-1] + 1;

                ver[i][j] = (i==0)? 1: ver[i-1][j] + 1;

            }

        }

    }

  

    // Начинаем с крайнего правого нижнего углового элемента и находим

    // самая большая ssubsquare с помощью hor [] [] и ver [] []

    for (int i = N-1; i>=1; i--)

    {

        for (int j = N-1; j>=1; j--)

        {

            // Находим меньшие значения в hor [] [] и ver [] []

            // Квадрат можно сделать только взяв меньший

            // значение

            int small = getMin(hor[i][j], ver[i][j]);

  

            // На данный момент мы уверены, что есть право

            // вертикальная линия и нижняя горизонтальная линия длины

            // хотя бы 'маленький'

  

            // Мы нашли большую площадь, если выполняются следующие условия

            // которые встретились:

            // 1) Если сторона квадрата больше макс.

            // 2) есть левая вертикальная линия длины> = 'small'

            // 3) Существует верхняя горизонтальная линия длины> = 'small'

            while (small > max)

            {

                if (ver[i][j-small+1] >= small &&

                    hor[i-small+1][j] >= small)

                {

                    max = small;

                }

                small--;

            }

        }

    }

    return max;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int mat[][N] =  {{'X', 'O', 'X', 'X', 'X', 'X'},

                     {'X', 'O', 'X', 'X', 'O', 'X'},

                     {'X', 'X', 'X', 'O', 'O', 'X'},

                     {'O', 'X', 'X', 'X', 'X', 'X'},

                     {'X', 'X', 'X', 'O', 'X', 'O'},

                     {'O', 'O', 'X', 'O', 'O', 'O'},

                    };

    cout << findSubSquare(mat);

    return 0;

}

Джава

// JAVA-программа для поиска
// самая большая окружающая площадь
// по 'X' в данной матрице
// 'O' и 'X'

import java.util.*;

  

class GFG 

{

    // Размер данного

    // матрица NXN

    static int N = 6;

      

    // Функция полезности для

    // найти минимум два числа

    static int getMin(int x, int y)

    { return (x < y) ? x : y; }

      

    // Возвращает размер максимума

    // размер субквадратной матрицы

    // в окружении 'X'

    static int findSubSquare(int mat[][])

    {

    int max = 0; // Инициализировать результат

  

    // Инициализируем левый верх

    // значение в hor [] [] и ver [] []

    int hor[][] = new int[N][N];

    int ver[][] = new int[N][N];

    hor[0][0] = ver[0][0] = 'X';

  

    // Заполняем значения в

    // hor [] [] и ver [] []

    for (int i = 0; i < N; i++)

    {

        for (int j = 0; j < N; j++)

        {

            if (mat[i][j] == 'O')

                ver[i][j] = hor[i][j] = 0;

            else

            {

                hor[i][j] = (j == 0) ? 1

                hor[i][j - 1] + 1;

                ver[i][j] = (i == 0) ? 1

                ver[i - 1][j] + 1;

            }

        }

    }

  

    // Начинаем с самого правого

    // самый нижний угловой элемент

    // и найти самый большой

    // квадрат с помощью

    // of hor [] [] и ver [] []

    for (int i = N - 1; i >= 1; i--)

    {

        for (int j = N - 1; j >= 1; j--)

        {

            // Находим меньшее из значений в

            // hor [] [] и ver [] [] Квадрат

            // можно сделать только взяв

            // меньшее значение

            int small = getMin(hor[i][j], 

                               ver[i][j]);

  

            // На данный момент мы уверены

            // что есть вертикаль справа

            // линия и нижняя горизонталь

            // строка длиной не менее 'small'.

  

            // Мы нашли большую площадь

            // если выполняются следующие условия

            // которые встретились:

            // 1) Если сторона квадрата

            // больше макс.

            // 2) есть левая вертикаль

            // строка длины> = 'small'

            // 3) есть верхняя горизонталь

            // строка длины> = 'small'

            while (small > max)

            {

                if (ver[i][j - small + 1] >= small &&

                    hor[i - small + 1][j] >= small)

                {

                    max = small;

                }

                small--;

            }

        }

    }

    return max;

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        // TODO Автоматически генерируемый метод заглушки

          

        int mat[][] = {{'X', 'O', 'X', 'X', 'X', 'X'},

                       {'X', 'O', 'X', 'X', 'O', 'X'},

                       {'X', 'X', 'X', 'O', 'O', 'X'},

                       {'O', 'X', 'X', 'X', 'X', 'X'},

                         {'X', 'X', 'X', 'O', 'X', 'O'},

                       {'O', 'O', 'X', 'O', 'O', 'O'}};

            System.out.println(findSubSquare(mat));

    }

}

  
// Этот код добавлен
// ChitraNayal

python3

# Программа Python3, чтобы найти самый большой
# subquare, окруженный 'X' в данном
# матрица из 'O' и 'X'

import math as mt

  
# Размер данной матрицы равен NXN

N = 6

  
# Полезная функция для поиска минимума
№ из двух чисел

def getMin(x, y):

    if x < y:

        return x

    else:

        return y

          
# Возвращает размер максимального размера
# квадратная матрица, окруженная 'X'

def findSubSquare(mat):

  

    Max = 0 # Инициализировать результат

  

    # Инициализировать левое верхнее значение

    # in hor [] [] и ver [] []

    hor = [[0 for i in range(N)] 

              for i in range(N)]

    ver = [[0 for i in range(N)] 

              for i in range(N)]

  

    if mat[0][0] == 'X':

        hor[0][0] = 1

        ver[0][0] = 1

  

    # Заполните значения в hor [] [] и ver [] []

    for i in range(N):

      

        for j in range(N):

          

            if (mat[i][j] == 'O'):

                ver[i][j], hor[i][j] = 0, 0

            else:

                if j == 0:

                    ver[i][j], hor[i][j] = 1, 1

                else:

                    (ver[i][j], 

                     hor[i][j]) = (ver[i - 1][j] + 1

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

  

    # Начинаем с самого правого-самого нижнего угла

    # элемент и найти самый большой ssubsquare

    # с помощью hor [] [] и ver [] []

    for i in range(N - 1, 0, -1):

      

        for j in range(N - 1, 0, -1):

          

            # Найдите меньшее из значений в hor [] [] и

            # ver [] []. Квадрат может быть сделан только

            # принимая меньшее значение

            small = getMin(hor[i][j], ver[i][j])

  

            # На данный момент, мы уверены, что там

            # - вертикальная линия справа и снизу

            # горизонтальная линия длиной не менее «маленькой».

  

            # Мы нашли большую площадь, если следующие

            # условия выполнены:

            # 1) Если сторона квадрата больше, чем Макс.

            # 2) Есть левая вертикальная линия

            # длины> = 'маленький'

            # 3) есть верхняя горизонтальная линия

            # длины> = 'маленький'

            while (small > Max):

              

                if (ver[i][j - small + 1] >= small and 

                    hor[i - small + 1][j] >= small):

                  

                    Max = small

                  

                small -= 1

              

    return Max

  
Код водителя

mat = [['X', 'O', 'X', 'X', 'X', 'X'],

       ['X', 'O', 'X', 'X', 'O', 'X'],

       ['X', 'X', 'X', 'O', 'O', 'X'],

       ['O', 'X', 'X', 'X', 'X', 'X'],

       ['X', 'X', 'X', 'O', 'X', 'O'],

       ['O', 'O', 'X', 'O', 'O', 'O']]

print(findSubSquare(mat))

  
# Этот код предоставлен
# Мохит Кумар 29

C #

// AC # программа для поиска
// самая большая окружающая площадь
// по 'X' в данной матрице
// 'O' и 'X'

using System;

  

class GFG 

{
// Размер данного
// матрица NXN

static int N = 6;

  
// Функция полезности для
// найти минимум два числа

static int getMin(int x, int y)

{ return (x < y) ? x : y; }

  
// Возвращает размер максимума
// размер субквадратной матрицы
// в окружении 'X'

static int findSubSquare(int[,] mat)

{

int max = 0; // Инициализировать результат

  
// Инициализируем левый верх
// значение в hor [] [] и ver [] []

int[,] hor = new int[N, N];

int[,] ver = new int[N, N];

hor[0, 0] = ver[0, 0] = 'X';

  
// Заполняем значения в
// hor [] [] и ver [] []

for (int i = 0; i < N; i++)

{

    for (int j = 0; j < N; j++)

    {

        if (mat[i, j] == 'O')

            ver[i, j] = hor[i, j] = 0;

        else 

        {

            hor[i, j] = (j == 0) ? 1 : 

            hor[i, j - 1] + 1;

            ver[i, j] = (i == 0) ? 1 : 

            ver[i - 1, j] + 1;

        }

    }

}

  
// Начинаем с самого правого
// самый нижний угловой элемент
// и найти самый большой
// квадрат с помощью
// of hor [] [] и ver [] []

for (int i = N - 1; i >= 1; i--)

{

    for (int j = N - 1; j >= 1; j--)

    {

        // Находим меньшее из значений в

        // hor [] [] и ver [] [] Квадрат

        // можно сделать только взяв

        // меньшее значение

        int small = getMin(hor[i, j], 

                           ver[i, j]);

  

        // На данный момент мы уверены

        // что есть вертикаль справа

        // линия и нижняя горизонталь

        // строка длиной не менее 'small'.

  

        // Мы нашли большую площадь

        // если выполняются следующие условия

        // которые встретились:

        // 1) Если сторона квадрата

        // больше макс.

        // 2) есть левая вертикаль

        // строка длины> = 'small'

        // 3) есть верхняя горизонталь

        // строка длины> = 'small'

        while (small > max)

        {

            if (ver[i, j - small + 1] >= small &&

                hor[i - small + 1, j] >= small)

            {

                max = small;

            }

            small--;

        }

    }

}

return max;

}

  
// Код драйвера

public static void Main() 

{

    // TODO Автоматически генерируемый метод заглушки

      

    int[,] mat = {{'X', 'O', 'X', 'X', 'X', 'X'},

                  {'X', 'O', 'X', 'X', 'O', 'X'},

                  {'X', 'X', 'X', 'O', 'O', 'X'},

                  {'O', 'X', 'X', 'X', 'X', 'X'},

                  {'X', 'X', 'X', 'O', 'X', 'O'},

                  {'O', 'O', 'X', 'O', 'O', 'O'}};

    Console.WriteLine(findSubSquare(mat));

}
}

  
// Этот код добавлен
// Аканкша Рай (Abby_akku)

PHP

<?php 
// PHP-программа для поиска
// самая большая площадь
// окружен 'X' в
// заданная матрица из 'O' и 'X'

  
// Размер данного
// матрица NXN

$N = 6;

  
// Полезная функция для поиска
// минимум двух чисел

function getMin($x, $y

    return ($x < $y) ? $x : $y

}

  
// Возвращает размер максимума
// размер субквадратной матрицы
// в окружении 'X'

function findSubSquare($mat)

{

    $max = 0; // Инициализировать результат

    $hor[0][0] = $ver[0][0] = ($mat[0][0] == 'X');

  

    // Заполняем значения в

    // $ hor и $ ver

    for ($i = 0; $i < $GLOBALS['N']; $i++)

    {

        for ($j = 0; $j < $GLOBALS['N']; $j++)

        {

            if ($mat[$i][$j] == 'O')

                $ver[$i][$j] = $hor[$i][$j] = 0;

            else

            {

                $hor[$i][$j] = ($j == 0) ? 1 : 

                                $hor[$i][$j - 1] + 1;

                $ver[$i][$j] = ($i == 0) ? 1 : 

                                $ver[$i - 1][$j] + 1;

            }

        }

    }

  

    // Начинаем с самого правого

    // самый нижний угловой элемент

    // и найти самый большой

    // подквадрат с помощью

    // $ hor и $ ver

    for ($i = $GLOBALS['N'] - 1; $i >= 1; $i--)

    {

        for ($j = $GLOBALS['N'] - 1; $j >= 1; $j--)

        {

            // Находим меньшее из значений в

            // $ hor и $ ver Квадратная банка

            // можно сделать только взяв

            // меньшее значение

            $small = getMin($hor[$i][$j],

                            $ver[$i][$j]);

  

            // На данный момент мы уверены

            // что есть вертикаль справа

            // линия и нижняя горизонталь

            // строка длиной не менее $ small.

  

            // Мы нашли большую площадь, если

            // выполняются следующие условия:

            // 1) Если сторона квадрата

            // больше чем макс.

            // 2) есть левая вертикаль

            // строка длины> = '$ small'

            // 3) есть верхняя горизонталь

            // строка длины> = '$ small'

            while ($small > $max)

            {

                if ($ver[$i][$j - $small + 1] >= $small &&

                    $hor[$i - $small + 1][$j] >= $small)

                {

                    $max = $small;

                }

                $small--;

            }

        }

    }

    return $max;

}

  
// Код драйвера

$mat = array(array('X', 'O', 'X', 'X', 'X', 'X'),

             array('X', 'O', 'X', 'X', 'O', 'X'),

             array('X', 'X', 'X', 'O', 'O', 'X'),

             array('O', 'X', 'X', 'X', 'X', 'X'),

             array('X', 'X', 'X', 'O', 'X', 'O'),

             array('O', 'O', 'X', 'O', 'O', 'O'));

echo findSubSquare($mat);

  
// Этот код добавлен
// ChitraNayal
?>


Выход:

4

Эта статья предоставлена Anuj . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Учитывая матрицу 'O' и 'X', найдите самый большой квадрат, окруженный 'X'

0.00 (0%) 0 votes