Dada una array donde cada elemento es ‘O’ o ‘X’, encuentre el subcuadrado más grande rodeado por ‘X’.
En el siguiente artículo, se supone que la array dada también es una array cuadrada. El código dado a continuación se puede extender fácilmente para arrays rectangulares.
Ejemplos:
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'
Una solución simple es considerar cada subarray cuadrada y verificar si tiene todos los bordes de las esquinas llenos de ‘X’. La complejidad temporal de esta solución es O(N 4 ).
Podemos resolver este problema en tiempo O(N 3 ) usando espacio adicional. La idea es crear dos arreglos auxiliares hor[N][N] y ver[N][N]. El valor almacenado en hor[i][j] es el número de caracteres horizontales continuos ‘X’ hasta mat[i][j] en mat[][]. De manera similar, el valor almacenado en ver[i][j] es el número de caracteres verticales continuos ‘X’ hasta mat[i][j] en mat[][].
Ejemplo:
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
Una vez que hemos llenado los valores en hor[][] y ver[][], comenzamos desde la esquina inferior derecha de la array y nos movemos hacia la esquina superior izquierda fila por fila. Para cada entrada visitada mat[i][j], comparamos los valores de hor[i][j] y ver[i][j], y elegimos el menor de dos ya que necesitamos un cuadrado. Deje que el menor de dos sea ‘pequeño’. Después de elegir el más pequeño de dos, comprobamos si ver[][] y hor[][] para los bordes izquierdo y superior respectivamente. Si tienen entradas para lo mismo, entonces encontramos un subcuadrado. De lo contrario, intentamos con small-1.
A continuación se muestra la implementación de la idea anterior.
C++
// A C++ program to find the largest subsquare
// surrounded by 'X' in a given matrix of 'O' and 'X'
#include <iostream>
using namespace std;
// Size of given matrix is N X N
#define N 6
// A utility function to find minimum of two numbers
int getMin(int x, int y) { return (x < y) ? x : y; }
// Returns size of maximum size subsquare matrix
// surrounded by 'X'
int findSubSquare(int mat[][N])
{
int max = 0; // Initialize result
// Initialize the left-top value in hor[][] and ver[][]
int hor[N][N], ver[N][N];
hor[0][0] = ver[0][0] = (mat[0][0] == 'X');
// Fill values in hor[][] and 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;
}
}
}
// Start from the rightmost-bottommost corner element
// and find the largest ssubsquare with the help of
// hor[][] and ver[][]
for (int i = N - 1; i >= 1; i--)
{
for (int j = N - 1; j >= 1; j--)
{
// Find smaller of values in hor[][] and ver[][]
// A Square can only be made by taking smaller
// value
int small = getMin(hor[i][j], ver[i][j]);
// At this point, we are sure that there is a
// right vertical line and bottom horizontal
// line of length at least 'small'.
// We found a bigger square if following
// conditions are met: 1)If side of square is
// greater than max. 2)There is a left vertical
// line of length >= 'small' 3)There is a top
// horizontal line of length >= 'small'
while (small > max)
{
if (ver[i][j - small + 1] >= small
&& hor[i - small + 1][j] >= small)
{
max = small;
}
small--;
}
}
}
return max;
}
// Driver code
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' },
};
// Function call
cout << findSubSquare(mat);
return 0;
}
Java
// A JAVA program to find the
// largest subsquare surrounded
// by 'X' in a given matrix of
// 'O' and 'X'
import java.util.*;
class GFG
{
// Size of given
// matrix is N X N
static int N = 6;
// A utility function to
// find minimum of two numbers
static int getMin(int x, int y)
{
return (x < y) ? x : y;
}
// Returns size of maximum
// size subsquare matrix
// surrounded by 'X'
static int findSubSquare(int mat[][])
{
int max = 0; // Initialize result
// Initialize the left-top
// value in hor[][] and ver[][]
int hor[][] = new int[N][N];
int ver[][] = new int[N][N];
hor[0][0] = ver[0][0] = 'X';
// Fill values in
// hor[][] and 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;
}
}
}
// Start from the rightmost-
// bottommost corner element
// and find the largest
// subsquare with the help
// of hor[][] and ver[][]
for (int i = N - 1; i >= 1; i--)
{
for (int j = N - 1; j >= 1; j--)
{
// Find smaller of values in
// hor[][] and ver[][] A Square
// can only be made by taking
// smaller value
int small = getMin(hor[i][j], ver[i][j]);
// At this point, we are sure
// that there is a right vertical
// line and bottom horizontal
// line of length at least 'small'.
// We found a bigger square
// if following conditions
// are met:
// 1)If side of square
// is greater than max.
// 2)There is a left vertical
// line of length >= 'small'
// 3)There is a top horizontal
// line of length >= 'small'
while (small > max)
{
if (ver[i][j - small + 1] >= small
&& hor[i - small + 1][j] >= small)
{
max = small;
}
small--;
}
}
}
return max;
}
// Driver Code
public static void main(String[] args)
{
// TODO Auto-generated method stub
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' } };
// Function call
System.out.println(findSubSquare(mat));
}
}
// This code is contributed
// by ChitraNayal
Python3
# A Python3 program to find the largest # subsquare surrounded by 'X' in a given # matrix of 'O' and 'X' import math as mt # Size of given matrix is N X N N = 6 # A utility function to find minimum # of two numbers def getMin(x, y): if x < y: return x else: return y # Returns size of Maximum size # subsquare matrix surrounded by 'X' def findSubSquare(mat): Max = 0 # Initialize result # Initialize the left-top value # in hor[][] and 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 # Fill values in hor[][] and 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) # Start from the rightmost-bottommost corner # element and find the largest ssubsquare # with the help of hor[][] and ver[][] for i in range(N - 1, 0, -1): for j in range(N - 1, 0, -1): # Find smaller of values in hor[][] and # ver[][]. A Square can only be made by # taking smaller value small = getMin(hor[i][j], ver[i][j]) # At this point, we are sure that there # is a right vertical line and bottom # horizontal line of length at least 'small'. # We found a bigger square if following # conditions are met: # 1)If side of square is greater than Max. # 2)There is a left vertical line # of length >= 'small' # 3)There is a top horizontal line # of length >= 'small' while (small > Max): if (ver[i][j - small + 1] >= small and hor[i - small + 1][j] >= small): Max = small small -= 1 return Max # Driver Code 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']] # Function call print(findSubSquare(mat)) # This code is contributed by # Mohit kumar 29
C#
// A C# program to find the
// largest subsquare surrounded
// by 'X' in a given matrix of
// 'O' and 'X'
using System;
class GFG
{
// Size of given
// matrix is N X N
static int N = 6;
// A utility function to
// find minimum of two numbers
static int getMin(int x, int y)
{
return (x < y) ? x : y;
}
// Returns size of maximum
// size subsquare matrix
// surrounded by 'X'
static int findSubSquare(int[, ] mat)
{
int max = 0; // Initialize result
// Initialize the left-top
// value in hor[][] and ver[][]
int[, ] hor = new int[N, N];
int[, ] ver = new int[N, N];
hor[0, 0] = ver[0, 0] = 'X';
// Fill values in
// hor[][] and 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;
}
}
}
// Start from the rightmost-
// bottommost corner element
// and find the largest
// subsquare with the help
// of hor[][] and ver[][]
for (int i = N - 1; i >= 1; i--)
{
for (int j = N - 1; j >= 1; j--)
{
// Find smaller of values in
// hor[][] and ver[][] A Square
// can only be made by taking
// smaller value
int small = getMin(hor[i, j], ver[i, j]);
// At this point, we are sure
// that there is a right vertical
// line and bottom horizontal
// line of length at least 'small'.
// We found a bigger square
// if following conditions
// are met:
// 1)If side of square
// is greater than max.
// 2)There is a left vertical
// line of length >= 'small'
// 3)There is a top horizontal
// line of length >= 'small'
while (small > max)
{
if (ver[i, j - small + 1] >= small
&& hor[i - small + 1, j] >= small)
{
max = small;
}
small--;
}
}
}
return max;
}
// Driver Code
public static void Main()
{
// TODO Auto-generated method stub
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' } };
// Function call
Console.WriteLine(findSubSquare(mat));
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
PHP
<?php
// A PHP program to find
// the largest subsquare
// surrounded by 'X' in a
// given matrix of 'O' and 'X'
// Size of given
// matrix is N X N
$N = 6;
// A utility function to find
// minimum of two numbers
function getMin($x, $y)
{
return ($x < $y) ? $x : $y;
}
// Returns size of maximum
// size subsquare matrix
// surrounded by 'X'
function findSubSquare($mat)
{
$max = 0; // Initialize result
$hor[0][0] = $ver[0][0] = ($mat[0][0] == 'X');
// Fill values in
// $hor and $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;
}
}
}
// Start from the rightmost-
// bottommost corner element
// and find the largest
// subsquare with the help of
// $hor and $ver
for ($i = $GLOBALS['N'] - 1; $i >= 1; $i--)
{
for ($j = $GLOBALS['N'] - 1; $j >= 1; $j--)
{
// Find smaller of values in
// $hor and $ver A Square can
// only be made by taking
// smaller value
$small = getMin($hor[$i][$j],
$ver[$i][$j]);
// At this point, we are sure
// that there is a right vertical
// line and bottom horizontal
// line of length at least '$small'.
// We found a bigger square if
// following conditions are met:
// 1)If side of square is
// greater than $max.
// 2)There is a left vertical
// line of length >= '$small'
// 3)There is a top horizontal
// line of length >= '$small'
while ($small > $max)
{
if ($ver[$i][$j - $small + 1] >= $small &&
$hor[$i - $small + 1][$j] >= $small)
{
$max = $small;
}
$small--;
}
}
}
return $max;
}
// Driver Code
$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'));
// Function call
echo findSubSquare($mat);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// A JavaScript program to find the
// largest subsquare surrounded
// by 'X' in a given matrix of
// 'O' and 'X'
// Size of given
// matrix is N X N
let N = 6;
// A utility function to
// find minimum of two numbers
function getMin(x,y)
{
return (x < y) ? x : y;
}
// Returns size of maximum
// size subsquare matrix
// surrounded by 'X'
function findSubSquare(mat)
{
let max = 0; // Initialize result
// Initialize the left-top
// value in hor[][] and ver[][]
let hor = new Array(N);
let ver = new Array(N);
for (let i = 0; i < N; i++)
{
hor[i]=new Array(N);
ver[i]=new Array(N);
for (let j = 0; j < N; j++)
{
hor[i][j]="";
ver[i][j]="";
}
}
hor[0][0] = 'X';
ver[0][0] = 'X';
// Fill values in
// hor[][] and ver[][]
for (let i = 0; i < N; i++)
{
for (let 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;
}
}
}
// Start from the rightmost-
// bottommost corner element
// and find the largest
// subsquare with the help
// of hor[][] and ver[][]
for (let i = N - 1; i >= 1; i--)
{
for (let j = N - 1; j >= 1; j--)
{
// Find smaller of values in
// hor[][] and ver[][] A Square
// can only be made by taking
// smaller value
let small = getMin(hor[i][j], ver[i][j]);
// At this point, we are sure
// that there is a right vertical
// line and bottom horizontal
// line of length at least 'small'.
// We found a bigger square
// if following conditions
// are met:
// 1)If side of square
// is greater than max.
// 2)There is a left vertical
// line of length >= 'small'
// 3)There is a top horizontal
// line of length >= 'small'
while (small > max)
{
if (ver[i][j - small + 1] >= small
&& hor[i - small + 1][j] >= small)
{
max = small;
}
small--;
}
}
}
return max;
}
// Driver Code
// TODO Auto-generated method stub
let 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']]
//Function call
document.write(findSubSquare(mat))
// This code is contributed by unknown2108
</script>
Producción
4
Complejidad temporal: O(N 2 ).
Espacio Auxiliar: O(N 2 )
Enfoque optimizado:
Una solución más optimizada sería calcular previamente el número de ‘X’ contiguas horizontal y verticalmente, en una array de pares denominada dp. Ahora, para cada entrada de dp tenemos un par (int, int) que denota la máxima ‘X’ contigua hasta ese punto, es decir
- dp[i][j].primero denota una ‘X’ contigua tomada horizontalmente hasta ese punto.
- dp[i][j].segundo denota una ‘X’ contigua tomada verticalmente hasta ese punto.
Ahora, se puede formar un cuadrado con dp[i][j] como la esquina inferior derecha, con lados de longitud máxima, min(dp[i][j].primero, dp[i][j].segundo)
Entonces, hacemos otra array maxside , que denotará el lado cuadrado máximo formado con la esquina inferior derecha como arr[i][j]. Intentaremos intuir un poco las propiedades de un cuadrado, es decir, todos los lados del cuadrado son iguales.
Almacenemos el valor máximo que se puede obtener, como val = min(dp[i][j].primero, dp[i][j].segundo). Desde el punto (i, j), retrocedemos horizontalmente por la distancia Val, y verificamos si el mínimo vertical contiguo ‘X’ hasta ese punto es igual a Val.
De manera similar, recorremos verticalmente hacia atrás la distancia Val y comprobamos si la mínima ‘X’ horizontal contigua hasta ese punto es igual a Val? Aquí estamos haciendo uso del hecho de que todos los lados del cuadrado son iguales.
Array de entrada:
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
Valor de la array dp:
(1,1) (0,0) (1,1) (2,7) (3,1) (4,1)
(1,2) (0,0) (1,2) (2,8) (0,0) (1,2)
(1,3) (2,1) (3,3) (0,0) (0,0) (1,3)
(0,0) (1,2) (2,4) (3,1) (4,1) (5,4)
(1,1) (2,3) (3,5) (0,0) (1,2) (0,0)
(0,0) (0,0) (1,6) (0,0) (0,0) (0,0)
A continuación se muestra la implementación de la idea anterior:
C++
// A C++ program to find the largest subsquare
// surrounded by 'X' in a given matrix of 'O' and 'X'
#include <bits/stdc++.h>
using namespace std;
// Size of given matrix is N X N
#define N 6
int maximumSubSquare(int arr[][N])
{
pair<int, int> dp[51][51];
int maxside[51][51];
// Initialize maxside with 0
memset(maxside, 0, sizeof(maxside));
int x = 0, y = 0;
// Fill the dp matrix horizontally.
// for contiguous 'X' increment the value of x,
// otherwise make it 0
for (int i = 0; i < N; i++)
{
x = 0;
for (int j = 0; j < N; j++)
{
if (arr[i][j] == 'X')
x += 1;
else
x = 0;
dp[i][j].first = x;
}
}
// Fill the dp matrix vertically.
// For contiguous 'X' increment the value of y,
// otherwise make it 0
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (arr[j][i] == 'X')
y += 1;
else
y = 0;
dp[j][i].second = y;
}
}
// Now check , for every value of (i, j) if sub-square
// is possible,
// traverse back horizontally by value val, and check if
// vertical contiguous
// 'X'enfing at (i , j-val+1) is greater than equal to
// val.
// Similarly, check if traversing back vertically, the
// horizontal contiguous
// 'X'ending at (i-val+1, j) is greater than equal to
// val.
int maxval = 0, val = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
val = min(dp[i][j].first, dp[i][j].second);
if (dp[i][j - val + 1].second >= val
&& dp[i - val + 1][j].first >= val)
maxside[i][j] = val;
else
maxside[i][j] = 0;
// store the final answer in maxval
maxval = max(maxval, maxside[i][j]);
}
}
// return the final answe.
return maxval;
}
// Driver code
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' },
};
// Function call
cout << maximumSubSquare(mat);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG
{
static int N = 6;
static int maximumSubSquare(int[][] arr)
{
int[][][] dp = new int[51][51][2];
int[][] maxside = new int[51][51];
// Initialize maxside with 0
for (int[] row : maxside)
Arrays.fill(row, 10);
int x = 0, y = 0;
// Fill the dp matrix horizontally.
// for contiguous 'X' increment the value of x,
// otherwise make it 0
for (int i = 0; i < N; i++)
{
x = 0;
for (int j = 0; j < N; j++)
{
if (arr[i][j] == 'X')
x += 1;
else
x = 0;
dp[i][j][0] = x;
}
}
// Fill the dp matrix vertically.
// For contiguous 'X' increment the value of y,
// otherwise make it 0
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (arr[j][i] == 'X')
y += 1;
else
y = 0;
dp[j][i][1] = y;
}
}
// Now check , for every value of (i, j) if sub-square
// is possible,
// traverse back horizontally by value val, and check if
// vertical contiguous
// 'X'enfing at (i , j-val+1) is greater than equal to
// val.
// Similarly, check if traversing back vertically, the
// horizontal contiguous
// 'X'ending at (i-val+1, j) is greater than equal to
// val.
int maxval = 0, val = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
val = Math.min(dp[i][j][0], dp[i][j][1]);
if (dp[i][j - val + 1][1] >= val
&& dp[i - val + 1][j][0] >= val)
maxside[i][j] = val;
else
maxside[i][j] = 0;
// store the final answer in maxval
maxval = Math.max(maxval, maxside[i][j]);
}
}
// return the final answe.
return maxval;
}
// Driver code
public static void main (String[] args)
{
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' },
};
// Function call
System.out.println(maximumSubSquare(mat));
}
}
// This code is contributed by rag2127.
Python3
# Python3 program to find the largest # subsquare surrounded by 'X' in a given # matrix of 'O' and 'X' # Size of given matrix is N X N N = 6 def maximumSubSquare(arr): dp = [[[-1, -1] for i in range(51)] for j in range(51)] # Initialize maxside with 0 maxside = [[0 for i in range(51)] for j in range(51)] x = 0 y = 0 # Fill the dp matrix horizontally. # for contiguous 'X' increment the # value of x, otherwise make it 0 for i in range(N): x = 0 for j in range(N): if (arr[i][j] == 'X'): x += 1 else: x = 0 dp[i][j][0] = x # Fill the dp matrix vertically. # For contiguous 'X' increment # the value of y, otherwise # make it 0 for i in range(N): for j in range(N): if (arr[j][i] == 'X'): y += 1 else: y = 0 dp[j][i][1] = y # Now check , for every value of (i, j) if sub-square # is possible, # traverse back horizontally by value val, and check if # vertical contiguous # 'X'enfing at (i , j-val+1) is greater than equal to # val. # Similarly, check if traversing back vertically, the # horizontal contiguous # 'X'ending at (i-val+1, j) is greater than equal to # val. maxval = 0 val = 0 for i in range(N): for j in range(N): val = min(dp[i][j][0], dp[i][j][1]) if (dp[i][j - val + 1][1] >= val and dp[i - val + 1][j][0] >= val): maxside[i][j] = val else: maxside[i][j] = 0 # Store the final answer in maxval maxval = max(maxval, maxside[i][j]) # Return the final answe. return maxval # Driver code 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' ] ] # Function call print(maximumSubSquare(mat)) # This code is contributed by avanitrachhadiya2155
C#
// A C# program to find the largest subsquare
// surrounded by 'X' in a given matrix of 'O' and 'X'
using System;
public class GFG{
static int N = 6;
static int maximumSubSquare(int[,] arr)
{
int[,,] dp = new int[51,51,2];
int[,] maxside = new int[51,51];
// Initialize maxside with 0
for(int i = 0; i < 51; i++)
{
for(int j = 0; j < 51; j++)
{
maxside[i,j] = 10;
}
}
int x = 0, y = 0;
// Fill the dp matrix horizontally.
// for contiguous 'X' increment the value of x,
// otherwise make it 0
for (int i = 0; i < N; i++)
{
x = 0;
for (int j = 0; j < N; j++)
{
if (arr[i,j] == 'X')
x += 1;
else
x = 0;
dp[i,j,0] = x;
}
}
// Fill the dp matrix vertically.
// For contiguous 'X' increment the value of y,
// otherwise make it 0
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (arr[j,i] == 'X')
y += 1;
else
y = 0;
dp[j,i,1] = y;
}
}
// Now check , for every value of (i, j) if sub-square
// is possible,
// traverse back horizontally by value val, and check if
// vertical contiguous
// 'X'enfing at (i , j-val+1) is greater than equal to
// val.
// Similarly, check if traversing back vertically, the
// horizontal contiguous
// 'X'ending at (i-val+1, j) is greater than equal to
// val.
int maxval = 0, val = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
val = Math.Min(dp[i,j,0], dp[i,j,1]);
if (dp[i,j - val + 1,1] >= val
&& dp[i - val + 1,j,0] >= val)
maxside[i,j] = val;
else
maxside[i,j] = 0;
// store the final answer in maxval
maxval = Math.Max(maxval, maxside[i,j]);
}
}
// return the final answe.
return maxval;
}
// Driver code
static public void Main (){
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' },
};
// Function call
Console.WriteLine(maximumSubSquare(mat));
}
}
// This code is contributed by patel2127
Javascript
<script>
/*package whatever //do not write package name here */
let N = 6;
function maximumSubSquare(arr)
{
let dp = new Array(51);
for(let i = 0; i < 51; i++)
{
dp[i] = new Array(51);
for(let j = 0; j < 51; j++)
{
dp[i][j] = new Array(2);
for(let k = 0; k < 2; k++)
{
dp[i][j][k] = 0;
}
}
}
let maxside = new Array(51);
for(let i = 0; i < 51; i++)
{
maxside[i] = new Array(51);
for(let j = 0; j < 51; j++)
{
maxside[i][j] = 10;
}
}
let x = 0, y = 0;
// Fill the dp matrix horizontally.
// for contiguous 'X' increment the value of x,
// otherwise make it 0
for (let i = 0; i < N; i++)
{
x = 0;
for (let j = 0; j < N; j++)
{
if (arr[i][j] == 'X')
x += 1;
else
x = 0;
dp[i][j][0] = x;
}
}
// Fill the dp matrix vertically.
// For contiguous 'X' increment the value of y,
// otherwise make it 0
for (let i = 0; i < N; i++)
{
for (let j = 0; j < N; j++)
{
if (arr[j][i] == 'X')
y += 1;
else
y = 0;
dp[j][i][1] = y;
}
}
// Now check , for every value of (i, j) if sub-square
// is possible,
// traverse back horizontally by value val, and check if
// vertical contiguous
// 'X'enfing at (i , j-val+1) is greater than equal to
// val.
// Similarly, check if traversing back vertically, the
// horizontal contiguous
// 'X'ending at (i-val+1, j) is greater than equal to
// val.
let maxval = 0, val = 0;
for (let i = 0; i < N; i++)
{
for (let j = 0; j < N; j++)
{
val = Math.min(dp[i][j][0], dp[i][j][1]);
if (dp[i][j - val + 1][1] >= val
&& dp[i - val + 1][j][0] >= val)
maxside[i][j] = val;
else
maxside[i][j] = 0;
// store the final answer in maxval
maxval = Math.max(maxval, maxside[i][j]);
}
}
// return the final answe.
return maxval;
}
// Driver code
let 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' ]
];
// Function call
document.write(maximumSubSquare(mat));
// This code is contributed by ab2127
</script>
Producción
4
Complejidad temporal: O(N 2 )
Espacio auxiliar : O(N 2 )
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA