Dada una letra de array [][] de tamaño N * M , compuesta de ‘#’ y ‘*’ y otra array de sello[][] de tamaño X * Y que contiene solo ‘$’ . La tarea es encontrar si todos los ‘*’ del más grande pueden ser reemplazados por ‘$’ superponiendo la array de sellos en la array de letras.
Nota: En una operación de superposición solo se puede considerar un área que tenga todos los caracteres como ‘*’ o ‘$’ .
Ejemplos:
Entrada: N = 3, M =5, X = 2, Y=2
Array de letras:
#****
#****
#****
Array de sellos:
$$
$$
Salida: Posible
explicación:
1er paso: Superponga la array de letras de (0,1) a (1,2), por lo tanto, la letra se verá como (recuerde que el lugar donde se coloca ‘#’ no se puede imponer)
#$$**
#$$**
#* ***
2.º paso: superponer array de letras de (0,3) a (1,4), la letra se convierte en
#$$$$
#$$$$
#****
3.er paso: dado que superponer sobre ‘$’ también es permitido, hacer superposición. Por lo tanto, estampar a continuación de (1,1) a (2,3)
#$$$$
#$$$$
#$$**
Paso final: vuelva a superponer y selle de (1,3) a (3,4)
#$$$$
#$$$$
#$$$$
Entrada: N = 3, M =5, X = 2, Y=2
Array de letras:
#**#*
#****
#****
Array de sellos:
$$
$$
Salida: Imposible
Explicación: El ‘# ‘ en (0,3) no se puede superponer.
Enfoque: el problema se puede resolver comprobando el número de caracteres ‘*’ entre dos ‘#’ o al final y al principio de una fila. Si alguno de estos recuentos es inferior a la longitud de la fila de la array de sellos, la solución no es posible. Lo mismo se aplica a las columnas también. Siga los pasos que se mencionan a continuación para implementar el enfoque:
- Bucle sobre la fila de array más grande completa sabiamente
- Para cada fila, cuente el número de ‘*’ consecutivos al principio o antes del final de la fila o entre dos ‘#’ . Si este conteo es más pequeño que la longitud de la fila de la array del sello, entonces es imposible y devuelve imposible como respuesta.
- Compruebe toda la array de letras de esta manera.
- Aplique el mismo proceso para las columnas también.
- Si la array de letras se puede superponer, devuelve verdadero. De lo contrario, devuelve falso.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if superimpose
// is possible or not
bool solution(int n, int m, int x, int y,
vector<string>& letter)
{
// Looping over rows
for (int i = 0; i < n; i++) {
// Initializing a length variable
// for counting the number of *
int len = 0;
for (int j = 0; j < m; j++) {
// If character encountered
// is *, then we
// increment the length
if (letter[i][j] == '*')
len++;
// If its not then there are
// two cases
else {
// 1st case is length is
// smaller than number of
// rows in stamp matrix,
// that would be impossible
// to stamp so return false
if (len != 0 && len < x)
return false;
// 2nd case is if its
// possible, reset len
else
len = 0;
}
}
}
// Do similarly for columns
// Looping over columns
for (int i = 0; i < m; i++) {
// Initializing length variable
int len = 0;
for (int j = 0; j < n; j++) {
// If encountered character
// is *, increment length
if (letter[j][i] == '*')
len++;
else {
// If its not possible
// return false
if (len != 0 && len < y)
return false;
// Otherwise reset len
else
len = 0;
}
}
}
return true;
}
// Driver code
int main()
{
int n = 3, x = 2, y = 2;
vector<string> letter = { "#***", "#***", "#***" };
int m = letter[0].size();
/*
Stamp Matrix:
$$
$$
A 2*2 matrix ( x*y)
*/
if (solution(n, m, x, y, letter))
cout << "Possible\n";
else
cout << "Impossible\n";
// 2nd case
vector<string> letter2 = { "#***", "#*#*", "#***" };
m = letter2[0].size();
if (solution(n, m, x, y, letter2))
cout << "Possible\n";
else
cout << "Impossible\n";
return 0;
}
// This code is contributed by rakeshsahni
Java
// Java code to implement the above approach
import java.util.*;
class GFG {
// Function to check if superimpose
// is possible or not
public static boolean solution(int n,
int m, int x,
int y,
String[] letter)
{
// Looping over rows
for (int i = 0; i < n; i++) {
// Initializing a length variable
// for counting the number of *
int len = 0;
for (int j = 0; j < m; j++) {
// If character encountered
// is *, then we
// increment the length
if (letter[i].charAt(j)
== '*')
len++;
// If its not then there are
// two cases
else {
// 1st case is length is
// smaller than number of
// rows in stamp matrix,
// that would be impossible
// to stamp so return false
if (len != 0 && len < x)
return false;
// 2nd case is if its
// possible, reset len
else
len = 0;
}
}
}
// Do similarly for columns
// Looping over columns
for (int i = 0; i < m; i++) {
// Initializing length variable
int len = 0;
for (int j = 0; j < n; j++) {
// If encountered character
// is *, increment length
if (letter[j].charAt(i)
== '*')
len++;
else {
// If its not possible
// return false
if (len != 0 && len < y)
return false;
// Otherwise reset len
else
len = 0;
}
}
}
return true;
}
// Driver code
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = 3, x = 2, y = 2;
String[] letter = { "#***",
"#***",
"#***" };
int m = letter[0].length();
/*
Stamp Matrix:
$$
$$
A 2*2 matrix ( x*y)
*/
if (solution(n, m, x, y, letter))
System.out.println("Possible");
else
System.out.println("Impossible");
// 2nd case
String[] letter2 = { "#***",
"#*#*",
"#***" };
m = letter2[0].length();
if (solution(n, m, x, y, letter2))
System.out.println("Possible");
else
System.out.println("Impossible");
}
}
Python3
# Python code to implement the above approach
# Function to check if superimpose
# is possible or not
def solution(n, m, x, y, letter):
# Looping over rows
for i in range(n):
# Initializing a length variable
# for counting the number of *
len = 0
for j in range(m):
# If character encountered
# is *, then we
# increment the length
if (letter[i][j] == '*'):
len += 1
# If its not then there are
# two cases
else:
# 1st case is length is
# smaller than number of
# rows in stamp matrix,
# that would be impossible
# to stamp so return false
if (len != 0 and len < x):
return False
# 2nd case is if its
# possible, reset len
else:
len = 0
# Do similarly for columns
# Looping over columns
for i in range(m):
# Initializing length variable
len = 0
for j in range(n):
# If encountered character
# is *, increment length
if (letter[j][i] == '*'):
len += 1
else:
# If its not possible
# return false
if (len != 0 and len < y):
return False
# Otherwise reset len
else:
len = 0
return True
# Driver code
n = 3
x = 2
y = 2
letter = ["#***", "#***", "#***"]
m = len(letter[0])
'''
Stamp Matrix:
$$
$$
A 2*2 matrix ( x*y)
'''
if (solution(n, m, x, y, letter)):
print("Possible")
else:
print("Impossible")
# 2nd case
letter2 = ["#***", "#*#*", "#***"]
m = len(letter2[0])
if (solution(n, m, x, y, letter2)):
print("Possible")
else:
print("Impossible")
# This code is contributed by Shubham Singh
C#
// C# code to implement the above approach
using System;
class GFG{
// Function to check if superimpose
// is possible or not
public static bool solution(int n, int m, int x, int y,
string[] letter)
{
// Looping over rows
for(int i = 0; i < n; i++)
{
// Initializing a length variable
// for counting the number of *
int len = 0;
for(int j = 0; j < m; j++)
{
// If character encountered
// is *, then we
// increment the length
if (letter[i][j] == '*')
len++;
// If its not then there are
// two cases
else
{
// 1st case is length is
// smaller than number of
// rows in stamp matrix,
// that would be impossible
// to stamp so return false
if (len != 0 && len < x)
return false;
// 2nd case is if its
// possible, reset len
else
len = 0;
}
}
}
// Do similarly for columns
// Looping over columns
for(int i = 0; i < m; i++)
{
// Initializing length variable
int len = 0;
for(int j = 0; j < n; j++)
{
// If encountered character
// is *, increment length
if (letter[j][i] == '*')
len++;
else
{
// If its not possible
// return false
if (len != 0 && len < y)
return false;
// Otherwise reset len
else
len = 0;
}
}
}
return true;
}
// Driver code
public static void Main(string[] args)
{
int n = 3, x = 2, y = 2;
string[] letter = { "#***", "#***", "#***" };
int m = letter.GetLength(0);
/*
Stamp Matrix:
$$
$$
A 2*2 matrix ( x*y)
*/
if (solution(n, m, x, y, letter))
Console.WriteLine("Possible");
else
Console.WriteLine("Impossible");
// 2nd case
String[] letter2 = { "#***", "#*#*", "#***" };
m = letter2.GetLength(0);
if (solution(n, m, x, y, letter2))
Console.WriteLine("Possible");
else
Console.WriteLine("Impossible");
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript code for the above approach
// Function to check if superimpose
// is possible or not
function solution(n, m, x, y,letter)
{
// Looping over rows
for (var i = 0; i < n; i++) {
// Initializing a length variable
// for counting the number of *
var len = 0;
for (var j = 0; j < m; j++) {
// If character encountered
// is *, then we
// increment the length
if (letter[i][j] == '*')
len++;
// If its not then there are
// two cases
else {
// 1st case is length is
// smaller than number of
// rows in stamp matrix,
// that would be impossible
// to stamp so return false
if (len != 0 && len < x)
return false;
// 2nd case is if its
// possible, reset len
else
len = 0;
}
}
}
// Do similarly for columns
// Looping over columns
for (var i = 0; i < m; i++) {
// Initializing length variable
var len = 0;
for (var j = 0; j < n; j++) {
// If encountered character
// is *, increment length
if (letter[j][i] == '*')
len++;
else {
// If its not possible
// return false
if (len != 0 && len < y)
return false;
// Otherwise reset len
else
len = 0;
}
}
}
return true;
}
// Driver code
var n = 3, x = 2, y = 2;
var letter = [ "#***", "#***", "#***" ];
var m = letter[0].length;
/*
Stamp Matrix:
$$
$$
A 2*2 matrix ( x*y)
*/
if (solution(n, m, x, y, letter))
document.write("Possible" + "<br>");
else
document.write("Impossible" + "<br>");
// 2nd case
var letter2 = [ "#***", "#*#*", "#***" ];
m = letter2[0].length;
if (solution(n, m, x, y, letter2))
document.write("Possible" + "<br>");
else
document.write("Impossible" + "<br>");
// This code is contributed by Shubham Singh
</script>
Producción
Impossible
Complejidad temporal: O(N*M)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por yogeshsherawat77 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA