Dadas dos arrays binarias, A[][] y B[][] de N×M . En una sola operación, se puede elegir una subarray (mínimo de 2 filas y 2c columnas) y cambiar la paridad de los elementos de esquina, es decir, 1 se puede cambiar a 0 y 0 se puede cambiar a 1 . La tarea es verificar si la array A se puede convertir en B usando cualquier número de operaciones.
Ejemplos:
Entrada: A[][] = {{0, 1, 0}, {0, 1, 0}, {1, 0, 0}}, B[][] = {{1, 0, 0},
{ 1, 0, 0}, {1, 0, 0}}
Salida: Sí
Elija la subarray cuya esquina superior izquierda sea (0, 0)
y cuya esquina inferior derecha sea (1, 1).
Cambiar la paridad de los elementos de esquina
de esta subarray convertirá A[][] en B[][]
Entrada: A[][] = {{0, 1, 0, 1}, {1, 0, 1 , 0}, {0, 1, 0, 1}},
B[][] = {{1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1 }}
Salida: No
Enfoque: Lo primero que hay que notar es que, a pesar de las conversiones, la paridad total de ambas arrays seguirá siendo la misma. Por lo tanto, verifique si a[i][j] no es lo mismo que b[i][j] y luego cambie la paridad de los elementos de esquina de la subarray cuya esquina superior izquierda es (0, 0) y la esquina inferior derecha es (yo, j) para 1 ≤ yo, j . Después de realizar el cambio de paridad para cada a[i][j] que no es igual a b[i][j], verifique si ambas arrays son iguales o no. Si son iguales, podemos cambiar A por B.
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;
#define N 3
#define M 3
// Boolean function that returns
// true or false
bool check(int a[N][M], int b[N][M])
{
// Traverse for all elements
for (int i = 1; i < N; i++) {
for (int j = 1; j < M; j++) {
// If both are not equal
if (a[i][j] != b[i][j]) {
// Change the parity of
// all corner elements
a[i][j] ^= 1;
a[0][0] ^= 1;
a[0][j] ^= 1;
a[i][0] ^= 1;
}
}
}
// Check if A is equal to B
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// Not equal
if (a[i][j] != b[i][j])
return false;
}
}
return true;
}
// Driver Code
int main()
{
// First binary matrix
int a[N][N] = { { 0, 1, 0 },
{ 0, 1, 0 },
{ 1, 0, 0 } };
// Second binary matrix
int b[N][N] = { { 1, 0, 0 },
{ 1, 0, 0 },
{ 1, 0, 0 } };
if (check(a, b))
cout << "Yes";
else
cout << "No";
}
Java
// Java implementation of the
// above approach
class GFG
{
static final int N = 3,M =3;
// Boolean function that returns
// true or false
static boolean check(int a[][], int b[][])
{
// Traverse for all elements
for (int i = 1; i < N; i++)
{
for (int j = 1; j < M; j++)
{
// If both are not equal
if (a[i][j] != b[i][j])
{
// Change the parity of
// all corner elements
a[i][j] ^= 1;
a[0][0] ^= 1;
a[0][j] ^= 1;
a[i][0] ^= 1;
}
}
}
// Check if A is equal to B
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// Not equal
if (a[i][j] != b[i][j])
return false;
}
}
return true;
}
// Driver Code
public static void main(String args[])
{
// First binary matrix
int a[][] = { { 0, 1, 0 },
{ 0, 1, 0 },
{ 1, 0, 0 } };
// Second binary matrix
int b[][] = { { 1, 0, 0 },
{ 1, 0, 0 },
{ 1, 0, 0 } };
if (check(a, b))
System.out.print( "Yes");
else
System.out.print( "No");
}
}
// This code is contributed by Arnab Kundu
Python3
# Python 3 implementation of the
# above approach
N = 3
M = 3
# Boolean function that returns
# true or false
def check(a, b):
# Traverse for all elements
for i in range(1, N, 1):
for j in range(1, M, 1):
# If both are not equal
if (a[i][j] != b[i][j]):
# Change the parity of
# all corner elements
a[i][j] ^= 1
a[0][0] ^= 1
a[0][j] ^= 1
a[i][0] ^= 1
# Check if A is equal to B
for i in range(N):
for j in range(M):
# Not equal
if (a[i][j] != b[i][j]):
return False
return True
# Driver Code
if __name__ == '__main__':
# First binary matrix
a = [[0, 1, 0],
[0, 1, 0],
[1, 0, 0]]
# Second binary matrix
b = [[1, 0, 0],
[1, 0, 0],
[1, 0, 0]]
if (check(a, b)):
print("Yes")
else:
print("No")
# This code is contributed by
# Surendra_Gangwar
C#
// C# implementation of the
// above approach
using System;
class GFG
{
static readonly int N = 3,M =3;
// Boolean function that returns
// true or false
static bool check(int [,]a, int [,]b)
{
// Traverse for all elements
for (int i = 1; i < N; i++)
{
for (int j = 1; j < M; j++)
{
// If both are not equal
if (a[i,j] != b[i,j])
{
// Change the parity of
// all corner elements
a[i,j] ^= 1;
a[0,0] ^= 1;
a[0,j] ^= 1;
a[i,0] ^= 1;
}
}
}
// Check if A is equal to B
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
// Not equal
if (a[i,j] != b[i,j])
return false;
}
}
return true;
}
// Driver Code
public static void Main(String []args)
{
// First binary matrix
int [,]a = { { 0, 1, 0 },
{ 0, 1, 0 },
{ 1, 0, 0 } };
// Second binary matrix
int [,]b = { { 1, 0, 0 },
{ 1, 0, 0 },
{ 1, 0, 0 } };
if (check(a, b))
Console.Write( "Yes");
else
Console.Write( "No");
}
}
// This code has been contributed by 29AjayKumar
PHP
<?php
// PHP implementation of the above approach
$N = 3;
$M = 3 ;
// Boolean function that returns
// true or false
function check($a, $b)
{
// Traverse for all elements
for ($i = 1; $i < $GLOBALS['N']; $i++)
{
for ($j = 1; $j < $GLOBALS['M']; $j++)
{
// If both are not equal
if ($a[$i][$j] != $b[$i][$j])
{
// Change the parity of
// all corner elements
$a[$i][$j] ^= 1;
$a[0][0] ^= 1;
$a[0][$j] ^= 1;
$a[$i][0] ^= 1;
}
}
}
// Check if A is equal to B
for ($i = 0; $i < $GLOBALS['N']; $i++)
{
for ($j = 0; $j < $GLOBALS['M']; $j++)
{
// Not equal
if ($a[$i][$j] != $b[$i][$j])
return false;
}
}
return true;
}
// Driver Code
// First binary matrix
$a = array(array( 0, 1, 0 ),
array( 0, 1, 0 ),
array( 1, 0, 0 ) );
// Second binary matrix
$b = array( array( 1, 0, 0 ),
array(1, 0, 0 ),
array( 1, 0, 0 ) );
if (check($a, $b))
echo "Yes";
else
echo "No";
// This code is contributed by Ryuga
?>
Javascript
<script>
// javascript implementation of the
// above approach
var N = 3, M = 3;
// Boolean function that returns
// true or false
function check(a , b) {
// Traverse for all elements
for (i = 1; i < N; i++) {
for (j = 1; j < M; j++) {
// If both are not equal
if (a[i][j] != b[i][j]) {
// Change the parity of
// all corner elements
a[i][j] ^= 1;
a[0][0] ^= 1;
a[0][j] ^= 1;
a[i][0] ^= 1;
}
}
}
// Check if A is equal to B
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
// Not equal
if (a[i][j] != b[i][j])
return false;
}
}
return true;
}
// Driver Code
// First binary matrix
var a = [ [ 0, 1, 0 ],
[ 0, 1, 0 ],
[ 1, 0, 0 ] ];
// Second binary matrix
var b = [ [ 1, 0, 0 ],
[ 1, 0, 0 ],
[ 1, 0, 0 ] ];
if (check(a, b))
document.write("Yes");
else
document.write("No");
// This code contributed by aashish1995
</script>
Yes
Complejidad de tiempo: O(N * M)
Espacio Auxiliar: O(1)