Dada una array binaria N*N arr[][] , la tarea es verificar si la array contiene un cuadrado de al menos tamaño 2 x 2 cuyos límites se componen de solo 0 s.
Ejemplos:
Entrada:
array[][] = {
{1, 1, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 1},
{0, 1, 1, 1, 0, 1} ,
{0, 0, 0, 1, 0, 1},
{0, 1, 1, 1, 0, 1},
{0, 0, 0, 0, 0, 1}
}
Salida: Verdadero
Explicación:
Dado que, arr[][] contiene una array cuadrada con todos los 0 en el límite, por lo que la respuesta es verdadera.
{
{ , , , , , },
{0, 0, 0, 0, 0, },
{0, , , , 0, },
{0, , , , 0, },
{0, , , , 0, },
{0, 0, 0, 0, 0, }
}Entrada:
array[][] = {
{1, 1, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 1},
{0, 1, 1, 1, 0, 1} ,
{0, 0, 0, 1, 1, 1},
{0, 1, 1, 1, 0, 1},
{0, 0, 0, 0, 0, 1}
}
Salida: Falso
Explicación: Hay ningún cuadrado en la array cuyos bordes estén formados solo por ceros.
Acercarse:
- Un cuadrado se define por sus filas superior e inferior y por sus columnas más a la izquierda y más a la derecha.
- Dado un par de filas y un par de columnas que forman un cuadrado válido, puede determinar fácilmente si el cuadrado relevante es un cuadrado de ceros con dos bucles for.
- Se requiere iterar sobre cada cuadrado válido en la array de entrada, arr[][].
- Podemos comenzar a iterar desde el cuadrado más externo e ir recursivamente hacia adentro en la array.
- Al movernos hacia adentro, desde (r1, c1) y (r2, c2) tenemos 5 opciones, que generarán una array cuadrada:
a) (r1 + 1, c1 + 1), (r2 – 1, c2 – 1)
b ) (r1, c1 + 1), (r2 – 1, c2)
c) (r1 + 1, c1), (r2, c2 – 1)
d) (r1 + 1, c1 + 1), (r2, c2)
e) (r1, c1), (r2 – 1, c2 – 1) - Dado que el problema tiene muchos subproblemas que se superponen , debemos usar caché/memoización para evitar cálculos duplicados.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
bool hasSquareOfZeroes(
vector<vector<int> >& matrix,
int r1, int c1, int r2, int c2,
unordered_map<string, bool>& cache);
bool isSquareOfZeroes(
vector<vector<int> >& matrix,
int r1, int c1,
int r2, int c2);
// Function checks if square
// with all 0's in boundary
// exists in the matrix
bool squareOfZeroes(
vector<vector<int> > matrix)
{
int lastIdx = matrix.size() - 1;
unordered_map<string, bool> cache;
return hasSquareOfZeroes(
matrix,
0, 0,
lastIdx,
lastIdx,
cache);
}
// Function iterate inward in
// the matrix and checks the
// square obtained and memoize/cache
// the result to avoid duplicate computation
// r1 is the top row,
// c1 is the left col
// r2 is the bottom row,
// c2 is the right
bool hasSquareOfZeroes(
vector<vector<int> >& matrix,
int r1, int c1, int r2, int c2,
unordered_map<string, bool>& cache)
{
if (r1 >= r2 || c1 >= c2)
return false;
string key = to_string(r1) + '-'
+ to_string(c1) + '-'
+ to_string(r2) + '-'
+ to_string(c2);
if (cache.find(key) != cache.end())
return cache[key];
cache[key]
= isSquareOfZeroes(
matrix, r1, c1, r2, c2)
|| hasSquareOfZeroes(
matrix, r1 + 1, c1 + 1,
r2 - 1, c2 - 1, cache)
|| hasSquareOfZeroes(
matrix, r1, c1 + 1,
r2 - 1, c2, cache)
|| hasSquareOfZeroes(
matrix, r1 + 1, c1,
r2, c2 - 1, cache)
|| hasSquareOfZeroes(
matrix, r1 + 1, c1 + 1,
r2, c2, cache)
|| hasSquareOfZeroes(
matrix, r1, c1,
r2 - 1, c2 - 1, cache);
return cache[key];
}
// Function checks if the
// boundary of the square
// consists of 0's
bool isSquareOfZeroes(
vector<vector<int> >& matrix,
int r1, int c1,
int r2, int c2)
{
for (int row = r1; row < r2 + 1; row++) {
if (matrix[row][c1] != 0
|| matrix[row][c2] != 0)
return false;
}
for (int col = c1; col < c2 + 1; col++) {
if (matrix[r1][col] != 0
|| matrix[r2][col] != 0)
return false;
}
return true;
}
// Driver Code
int main()
{
vector<vector<int> > matrix{
{ 1, 1, 1, 0, 1, 0 },
{ 0, 0, 0, 0, 0, 1 },
{ 0, 1, 1, 1, 0, 1 },
{ 0, 0, 0, 1, 0, 1 },
{ 0, 1, 1, 1, 0, 1 },
{ 0, 0, 0, 0, 0, 1 }
};
int ans;
ans = squareOfZeroes(matrix);
if (ans == 1) {
cout << "True" << endl;
}
else {
cout << "False" << endl;
}
}
Java
// Java implementation of the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function checks if square
// with all 0's in boundary
// exists in the matrix
static int squareOfZeroes(int[][] matrix)
{
int lastIdx = matrix.length - 1;
Map<String, Boolean> cache
= new HashMap<String, Boolean>();
return (hasSquareOfZeroes(matrix, 0, 0, lastIdx,
lastIdx, cache)) ? 1 : 0;
}
// Function iterate inward in
// the matrix and checks the
// square obtained and memoize/cache
// the result to avoid duplicate computation
// r1 is the top row,
// c1 is the left col
// r2 is the bottom row,
// c2 is the right
static boolean hasSquareOfZeroes(int[][] matrix, int r1, int c1,
int r2, int c2,
Map<String, Boolean> cache)
{
if (r1 >= r2 || c1 >= c2)
return false;
String key = r1 + "-" + c1 +
"-" + r2 + "-" + c2;
if (cache.containsKey(key))
return cache.get(key);
cache.put(
key,
isSquareOfZeroes(matrix, r1, c1, r2, c2)
|| hasSquareOfZeroes(matrix, r1 + 1, c1 + 1,
r2 - 1, c2 - 1, cache)
|| hasSquareOfZeroes(matrix, r1, c1 + 1,
r2 - 1, c2, cache)
|| hasSquareOfZeroes(matrix, r1 + 1, c1, r2,
c2 - 1, cache)
|| hasSquareOfZeroes(matrix, r1 + 1, c1 + 1,
r2, c2, cache)
|| hasSquareOfZeroes(matrix, r1, c1, r2 - 1,
c2 - 1, cache));
return cache.get(key);
}
// Function checks if the
// boundary of the square
// consists of 0's
static boolean isSquareOfZeroes(int[][] matrix,
int r1, int c1,
int r2, int c2)
{
for (int row = r1; row < r2 + 1; row++)
{
if (matrix[row][c1] != 0
|| matrix[row][c2] != 0)
return false;
}
for (int col = c1; col < c2 + 1; col++)
{
if (matrix[r1][col] != 0
|| matrix[r2][col] != 0)
return false;
}
return true;
}
// Driver Code
public static void main(String[] args)
{
int[][] matrix = {
{ 1, 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0, 1 },
{ 0, 1, 1, 1, 0, 1 }, { 0, 0, 0, 1, 0, 1 },
{ 0, 1, 1, 1, 0, 1 }, { 0, 0, 0, 0, 0, 1 }
};
int ans;
ans = squareOfZeroes(matrix);
if (ans == 1)
{
System.out.println("True");
}
else
{
System.out.println("False");
}
}
}
// This code is contributed by jitin
Python3
# Python3 implementation of the above approach
# Function checks if square
# with all 0's in boundary
# exists in the matrix
def squareOfZeroes():
global matrix, cache
lastIdx = len(matrix) - 1
return hasSquareOfZeroes(0, 0, lastIdx,
lastIdx)
# Function iterate inward in
# the matrix and checks the
# square obtained and memoize/cache
# the result to avoid duplicate computation
# r1 is the top row,
# c1 is the left col
# r2 is the bottom row,
# c2 is the right
def hasSquareOfZeroes(r1, c1, r2, c2):
global matrix, cache
if (r1 >= r2 or c1 >= c2):
return False
key = (str(r1) + '-' + str(c1) + '-' +
str(r2) + '-' + str(c2))
if (key in cache):
return cache[key]
cache[key] = (isSquareOfZeroes(r1, c1, r2, c2) or
hasSquareOfZeroes(r1 + 1, c1 + 1,
r2 - 1, c2 - 1))
cache[key] = (cache[key] or
hasSquareOfZeroes(r1, c1 + 1,
r2 - 1, c2) or
hasSquareOfZeroes(r1 + 1, c1,
r2, c2 - 1))
cache[key] = (cache[key] or
hasSquareOfZeroes(r1 + 1, c1 + 1,
r2, c2) or
hasSquareOfZeroes(r1, c1, r2 - 1,
c2 - 1))
return cache[key]
# Function checks if the
# boundary of the square
# consists of 0's
def isSquareOfZeroes(r1, c1, r2, c2):
global matrix
for row in range(r1, r2 + 1):
if (matrix[row][c1] != 0 or
matrix[row][c2] != 0):
return False
for col in range(c1, c2 + 1):
if (matrix[r1][col] != 0 or
matrix[r2][col] != 0):
return False
return True
# Driver Code
if __name__ == '__main__':
cache = {}
matrix = [ [ 1, 1, 1, 0, 1, 0 ],
[ 0, 0, 0, 0, 0, 1 ],
[ 0, 1, 1, 1, 0, 1 ],
[ 0, 0, 0, 1, 0, 1 ],
[ 0, 1, 1, 1, 0, 1 ],
[ 0, 0, 0, 0, 0, 1 ] ]
ans = squareOfZeroes()
if (ans == 1):
print("True")
else:
print("False")
# This code is contributed by mohit kumar 29
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function checks if square
// with all 0's in boundary
// exists in the matrix
static int squareOfZeroes(int[,] matrix)
{
int lastIdx = matrix.GetLength(0) - 1;
Dictionary<string, bool> cache = new Dictionary<string, bool>();
if(hasSquareOfZeroes(matrix, 0, 0, lastIdx,lastIdx, cache))
{
return 1;
}
else
{
return 0;
}
}
// Function iterate inward in
// the matrix and checks the
// square obtained and memoize/cache
// the result to avoid duplicate computation
// r1 is the top row,
// c1 is the left col
// r2 is the bottom row,
// c2 is the right
static bool hasSquareOfZeroes(int[,] matrix, int r1,
int c1,int r2, int c2,
Dictionary<string, bool> cache)
{
if (r1 >= r2 || c1 >= c2)
{
return false;
}
string key = r1 + "-" + c1 + "-" + r2 + "-" + c2;
if (cache.ContainsKey(key))
{
return cache[key];
}
cache[key] = (isSquareOfZeroes(matrix, r1, c1, r2, c2) ||
hasSquareOfZeroes(matrix, r1 + 1, c1 + 1,
r2 - 1, c2 - 1, cache) ||
hasSquareOfZeroes(matrix, r1, c1 + 1,r2 - 1,
c2, cache) ||
hasSquareOfZeroes(matrix, r1 + 1, c1, r2,
c2 - 1, cache) ||
hasSquareOfZeroes(matrix, r1 + 1, c1 + 1,
r2, c2, cache) ||
hasSquareOfZeroes(matrix, r1, c1, r2 - 1,
c2 - 1, cache));
return cache[key];
}
// Function checks if the
// boundary of the square
// consists of 0's
static bool isSquareOfZeroes(int[,] matrix, int r1,
int c1,int r2, int c2)
{
for (int row = r1; row < r2 + 1; row++)
{
if (matrix[row,c1] != 0 || matrix[row,c2] != 0)
{
return false;
}
}
for (int col = c1; col < c2 + 1; col++)
{
if (matrix[r1,col] != 0 || matrix[r2,col] != 0)
{
return false;
}
}
return true;
}
// Driver Code
static public void Main ()
{
int[,] matrix = {{ 1, 1, 1, 0, 1, 0 },
{ 0, 0, 0, 0, 0, 1 },
{ 0, 1, 1, 1, 0, 1 },
{ 0, 0, 0, 1, 0, 1 },
{ 0, 1, 1, 1, 0, 1 },
{ 0, 0, 0, 0, 0, 1 }};
int ans;
ans = squareOfZeroes(matrix);
if(ans == 1)
{
Console.WriteLine("True");
}
else
{
Console.WriteLine("False");
}
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript implementation of the above approach
// Function checks if square
// with all 0's in boundary
// exists in the matrix
function squareOfZeroes( matrix)
{
var lastIdx = matrix.length - 1;
var cache = new Map();
return hasSquareOfZeroes(
matrix,
0, 0,
lastIdx,
lastIdx,
cache);
}
// Function iterate inward in
// the matrix and checks the
// square obtained and memoize/cache
// the result to avoid duplicate computation
// r1 is the top row,
// c1 is the left col
// r2 is the bottom row,
// c2 is the right
function hasSquareOfZeroes(matrix, r1, c1, r2, c2, cache)
{
if (r1 >= r2 || c1 >= c2)
return false;
var key = (r1.toString()) + '-'
+ (c1.toString()) + '-'
+ (r2.toString()) + '-'
+ (c2.toString());
if (cache.has(key))
return cache.get(key);
cache[key]
= isSquareOfZeroes(
matrix, r1, c1, r2, c2)
|| hasSquareOfZeroes(
matrix, r1 + 1, c1 + 1,
r2 - 1, c2 - 1, cache)
|| hasSquareOfZeroes(
matrix, r1, c1 + 1,
r2 - 1, c2, cache)
|| hasSquareOfZeroes(
matrix, r1 + 1, c1,
r2, c2 - 1, cache)
|| hasSquareOfZeroes(
matrix, r1 + 1, c1 + 1,
r2, c2, cache)
|| hasSquareOfZeroes(
matrix, r1, c1,
r2 - 1, c2 - 1, cache);
return cache[key];
}
// Function checks if the
// boundary of the square
// consists of 0's
function isSquareOfZeroes(matrix, r1, c1, r2, c2)
{
for (var row = r1; row < r2 + 1; row++) {
if (matrix[row][c1] != 0
|| matrix[row][c2] != 0)
return false;
}
for (var col = c1; col < c2 + 1; col++) {
if (matrix[r1][col] != 0
|| matrix[r2][col] != 0)
return false;
}
return true;
}
// Driver Code
var matrix = [
[ 1, 1, 1, 0, 1, 0 ],
[ 0, 0, 0, 0, 0, 1 ],
[ 0, 1, 1, 1, 0, 1 ],
[ 0, 0, 0, 1, 0, 1 ],
[ 0, 1, 1, 1, 0, 1 ],
[ 0, 0, 0, 0, 0, 1 ]
];
var ans;
ans = squareOfZeroes(matrix);
if (ans == 1) {
document.write( "True");
}
else {
document.write( "False" );
}
</script>
Producción:
True
Complejidad de tiempo: O (N ^ 4), ya que estamos usando bucles anidados para atravesar N ^ 4 veces.
Complejidad espacial: O (N ^ 3), ya que estamos usando espacio adicional.
Enfoque eficiente: para optimizar el enfoque anterior, debemos seguir los pasos a continuación:
- Necesitamos precalcular dos valores para cada elemento de la array: la cantidad de 0 a la derecha de cada elemento (incluido el elemento en sí) y la cantidad de 0 debajo de cada elemento (incluido el elemento en sí).
- Podemos calcular estos valores iterando a través de la array comenzando en la esquina inferior derecha y subiendo recorriendo cada fila de derecha a izquierda.
- Una vez que hemos calculado la array, podemos verificar el límite del cuadrado si está compuesto por todos los 0 en tiempo constante.
- Para verificar el límite del cuadrado, solo necesitamos mirar la cantidad de 0 debajo de las dos esquinas superiores de cualquier cuadrado y la cantidad de 0 a la derecha de las dos esquinas izquierdas del mismo cuadrado.