Dadas dos arrays binarias mat[][] y target[][] de dimensiones N * M , la tarea es encontrar el costo mínimo para convertir la array mat[][] en target[][] usando las siguientes operaciones:
- Voltee una columna en particular en mat[][] de modo que todos los 1 se conviertan en 0 y viceversa. El coste de esta operación es de 1 .
- Reordenar las filas de mat[][] . El coste de esta operación es 0.
Si no es posible convertir la array mat[][] a target[][] , imprima “-1” .
Ejemplos:
Entrada: mat[][] = {{0, 0}, {1, 0}, {1, 1}}, target[][] = {{0, 1}, {1, 0}, {1, 1}}
Salida: 1
Explicación:
Paso 1: Reordene las filas 2 y 3 para modificar mat [][] a {{0, 0}, {1, 1}, {1, 0}}. Costo = 0
Paso 2: Da la vuelta a la segunda columna. mat[][] se modifica a {{0, 1}, {1, 0}, {1, 1}}, que es igual a target[][]. Costo = 1Entrada: mat[][] = {{0, 0, 0}, {1, 0, 1}, {1, 1, 0}}, target[][] = {{0, 0, 1}, { 1, 0, 1}, {1, 1, 1}}
Salida: -1
Enfoque: La idea es convertir las filas de las arrays dadas en conjuntos de bits y luego encontrar el costo mínimo de operación para igualar las arrays. A continuación se muestran los pasos:
- Primero, convierta las filas de mat[][] en números binarios usando un conjunto de bits.
- Después de completar el paso anterior, busque todas las filas posibles que puedan ser la primera fila de la array de destino.
- El número de giros necesarios para convertir la fila de mat[][] en tar[][] es el recuento de bits establecidos en el valor Bitwise XOR de los conjuntos de bits.
- Calcule Bitwise XOR de cada fila con el patrón de volteo y verifique si la nueva array, cuando se ordena, es igual a la array de destino [][] ordenada o no.
- Si son iguales, entonces almacena el número de vueltas.
- Calcule todo el recuento de lanzamientos en los pasos anteriores y devuelva el mínimo entre ellos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Custom comparator to sort vector
// of bitsets
bool static cmp(bitset<105>& p1,
bitset<105>& p2)
{
return p1.to_string() < p2.to_string();
}
// Function to convert the given
// matrix into the target matrix
int minCost(vector<vector<int> >& a,
vector<vector<int> >& t)
{
// Number of rows and columns
int n = a.size();
int m = a[0].size();
vector<bitset<105> > mat(n), tar(n);
// Iterate over rows
for (int i = 0; i < n; i++) {
string s;
for (int j = 0; j < m; j++) {
s += char(a[i][j] + '0');
}
mat[i] = bitset<105>(s);
}
// Iterate over rows
for (int i = 0; i < n; i++) {
string s;
for (int j = 0; j < m; j++) {
s += char(t[i][j] + '0');
}
tar[i] = bitset<105>(s);
}
// Sort the matrix
sort(tar.begin(), tar.end(), cmp);
int ans = INT_MAX;
// Check all possible rows as the
// first row of target
for (int i = 0; i < n; i++) {
vector<bitset<105> > copy(mat);
// Get the flip pattern
auto flip = copy[i] ^ tar[0];
for (auto& row : copy)
row ^= flip;
sort(copy.begin(), copy.end(), cmp);
// Number of flip operations
// is the count of set bits in flip
if (copy == tar)
ans = min(ans, (int)flip.count());
}
// If it is not possible
if (ans == INT_MAX)
return -1;
// Return the answer
return ans;
}
// Driver Code
int main()
{
// Given matrices
vector<vector<int> > matrix{ { 0, 0 },
{ 1, 0 },
{ 1, 1 } };
vector<vector<int> > target{ { 0, 1 },
{ 1, 0 },
{ 1, 1 } };
// Function Call
cout << minCost(matrix, target);
}
1
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(N * M)
Publicación traducida automáticamente
Artículo escrito por rohitpal210 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA