Dada una array binaria M[][] de dimensiones N x N , la tarea es hacer que cada par de celdas adyacentes en la misma fila o columna de la array dada sean distintas intercambiando el número mínimo de filas o columnas.
Ejemplos
Entrada: M[][] = {{0, 1, 1, 0}, {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 0, 0, 1}}, N = 4
Salida: 2
Explicación:
Paso 1: Intercambiar las filas 2 y 3 modifica la array a la siguiente representación:
M[][] = { { 0, 1, 1, 0},
{ 1, 0, 0, 1} ,
{ 0, 1, 1, 0},
{ 1, 0, 0, 1} }
Paso 1: intercambiar la primera y la segunda columna modifica la array a la siguiente representación:
M[][] = { { 1, 0, 1 , 0},
{ 0, 1, 0, 1},
{ 1, 0, 1, 0},
{ 0, 1, 0, 1} }Entrada: M[][] = {{0, 1, 1}, {1, 1, 0}, {1, 0, 0}, {1, 1, 1}}, N = 3
Salida: -1
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- En la array deseada, cualquier subarray que comience desde una esquina debe tener Bitwise XOR de todas las celdas igual a 0 .
- También se puede observar que debe haber como máximo dos tipos de secuencias que deben estar presentes en una fila o columna , es decir, {0, 1, 0, 1} y {1, 0, 1, 1}. Por lo tanto, una secuencia puede generarse a partir de la otra intercambiando el valor XOR de esa secuencia con 1 .
- Por lo tanto, al hacer solo la primera columna y la primera fila de acuerdo con el formato requerido, se minimizarán los intercambios totales requeridos.
Siga los pasos a continuación para resolver el problema:
- Recorra la array M[][] y verifique si bit a bit xor de todos los elementos M[i][0] , M[0][j] , M[0][0] y M[i][j] es 1 luego devuelve -1 .
- Inicialice las variables rowSum , colSum , rowSwap y colSwap con 0 .
- Recorra el rango [0, N-1] e incremente rowSum en M[i][0] , colSum en M[0][i] e incremente rowSwap en 1 si M[i][0] es igual a i% 2 y colSwap por 1 si M[0][i] es igual a i%2 .
- Si rowSum no es igual a N/2 o (N+1)/2 , devuelva -1 .
- Si colSum no es igual a N/2 o (N+1)/2 , devuelva -1 .
- Asigne colSwap = N – colSwap if, N%2 y colSwap%2 ambos no son iguales a 0 y rowSwap = N – rowSwap if, N%2 and rowSwap%2 ambos no son iguales a 0.
- Asigne colSwap igual al mínimo de colSwap y N-colSwap , y rowSwap igual al mínimo de rowSwap y N-rowSwap .
- Finalmente, imprima el resultado como (rowSum+colSum)/2 .
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; // Function to return number of moves // to convert matrix into chessboard int minSwaps(vector<vector<int> >& b) { // Size of the matrix int n = b.size(); // Traverse the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (b[0][0] ^ b[0][j] ^ b[i][0] ^ b[i][j]) return -1; } } // Initialize rowSum to count 1s in row int rowSum = 0; // Initialize colSum to count 1s in column int colSum = 0; // To store no. of rows to be corrected int rowSwap = 0; // To store no. of columns to be corrected int colSwap = 0; // Traverse in the range [0, N-1] for (int i = 0; i < n; i++) { rowSum += b[i][0]; colSum += b[0][i]; rowSwap += b[i][0] == i % 2; colSwap += b[0][i] == i % 2; } // Check if rows is either N/2 or // (N+1)/2 and return -1 if (rowSum != n / 2 && rowSum != (n + 1) / 2) return -1; // Check if rows is either N/2 // or (N+1)/2 and return -1 if (colSum != n / 2 && colSum != (n + 1) / 2) return -1; // Check if N is odd if (n % 2 == 1) { // Check if column required to be // corrected is odd and then // assign N-colSwap to colSwap if (colSwap % 2) colSwap = n - colSwap; // Check if rows required to // be corrected is odd and then // assign N-rowSwap to rowSwap if (rowSwap % 2) rowSwap = n - rowSwap; } else { // Take min of colSwap and N-colSwap colSwap = min(colSwap, n - colSwap); // Take min of rowSwap and N-rowSwap rowSwap = min(rowSwap, n - rowSwap); } // Finally return answer return (rowSwap + colSwap) / 2; } // Driver Code int main() { // Given matrix vector<vector<int> > M = { { 0, 1, 1, 0 }, { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1 } }; // Function Call int ans = minSwaps(M); // Print answer cout << ans; }
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to return number of moves // to convert matrix into chessboard public static int minSwaps(int[][] b) { // Size of the matrix int n = b.length; // Traverse the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if ((b[0][0] ^ b[0][j] ^ b[i][0] ^ b[i][j]) == 1) { return -1; } } } // Initialize rowSum to count 1s in row int rowSum = 0; // Initialize colSum to count 1s in column int colSum = 0; // To store no. of rows to be corrected int rowSwap = 0; // To store no. of columns to be corrected int colSwap = 0; // Traverse in the range [0, N-1] for (int i = 0; i < n; i++) { rowSum += b[i][0]; colSum += b[0][i]; int cond1 = 0; int cond2 = 0; if(b[i][0] == i % 2) cond1 = 1; if(b[0][i] == i % 2) cond2 = 1; rowSwap += cond1; colSwap += cond2; } // Check if rows is either N/2 or // (N+1)/2 and return -1 if (rowSum != n / 2 && rowSum != (n + 1) / 2) return -1; // Check if rows is either N/2 // or (N+1)/2 and return -1 if (colSum != n / 2 && colSum != (n + 1) / 2) return -1; // Check if N is odd if (n % 2 == 1) { // Check if column required to be // corrected is odd and then // assign N-colSwap to colSwap if ((colSwap % 2) == 1) colSwap = n - colSwap; // Check if rows required to // be corrected is odd and then // assign N-rowSwap to rowSwap if ((rowSwap % 2) == 1) rowSwap = n - rowSwap; } else { // Take min of colSwap and N-colSwap colSwap = Math.min(colSwap, n - colSwap); // Take min of rowSwap and N-rowSwap rowSwap = Math.min(rowSwap, n - rowSwap); } // Finally return answer return (rowSwap + colSwap) / 2; } // Driver Code public static void main (String[] args) { // Given matrix int[][] M = { { 0, 1, 1, 0 }, { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1 } }; // Function Call int ans = minSwaps(M); // Print answer System.out.println(ans); } } // This code is contributed by rohitsingh07052
Python3
# Python3 program for the above approach # Function to return number of moves # to convert matrix into chessboard def minSwaps(b): # Size of the matrix n = len(b) # Traverse the matrix for i in range(n): for j in range(n): if (b[0][0] ^ b[0][j] ^ b[i][0] ^ b[i][j]): return -1 # Initialize rowSum to count 1s in row rowSum = 0 # Initialize colSum to count 1s in column colSum = 0 # To store no. of rows to be corrected rowSwap = 0 # To store no. of columns to be corrected colSwap = 0 # Traverse in the range [0, N-1] for i in range(n): rowSum += b[i][0] colSum += b[0][i] rowSwap += b[i][0] == i % 2 colSwap += b[0][i] == i % 2 # Check if rows is either N/2 or # (N+1)/2 and return -1 if (rowSum != n // 2 and rowSum != (n + 1) // 2): return -1 # Check if rows is either N/2 # or (N+1)/2 and return -1 if (colSum != n // 2 and colSum != (n + 1) // 2): return -1 # Check if N is odd if (n % 2 == 1): # Check if column required to be # corrected is odd and then # assign N-colSwap to colSwap if (colSwap % 2): colSwap = n - colSwap # Check if rows required to # be corrected is odd and then # assign N-rowSwap to rowSwap if (rowSwap % 2): rowSwap = n - rowSwap else: # Take min of colSwap and N-colSwap colSwap = min(colSwap, n - colSwap) # Take min of rowSwap and N-rowSwap rowSwap = min(rowSwap, n - rowSwap) # Finally return answer return (rowSwap + colSwap) // 2 # Driver Code if __name__ == "__main__": # Given matrix M = [ [ 0, 1, 1, 0 ], [ 0, 1, 1, 0 ], [ 1, 0, 0, 1 ], [ 1, 0, 0, 1 ] ] # Function Call ans = minSwaps(M) # Print answer print(ans) # This code is contributed by chitranayal
C#
// C# program for the above approach using System; class GFG { // Function to return number of moves // to convert matrix into chessboard public static int minSwaps(int[,] b) { // Size of the matrix int n = b.GetLength(0); // Traverse the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if ((b[0, 0] ^ b[0, j] ^ b[i, 0] ^ b[i, j]) == 1) { return -1; } } } // Initialize rowSum to count 1s in row int rowSum = 0; // Initialize colSum to count 1s in column int colSum = 0; // To store no. of rows to be corrected int rowSwap = 0; // To store no. of columns to be corrected int colSwap = 0; // Traverse in the range [0, N-1] for (int i = 0; i < n; i++) { rowSum += b[i, 0]; colSum += b[0, i]; int cond1 = 0; int cond2 = 0; if(b[i, 0] == i % 2) cond1 = 1; if(b[0, i] == i % 2) cond2 = 1; rowSwap += cond1; colSwap += cond2; } // Check if rows is either N/2 or // (N+1)/2 and return -1 if (rowSum != n / 2 && rowSum != (n + 1) / 2) return -1; // Check if rows is either N/2 // or (N+1)/2 and return -1 if (colSum != n / 2 && colSum != (n + 1) / 2) return -1; // Check if N is odd if (n % 2 == 1) { // Check if column required to be // corrected is odd and then // assign N-colSwap to colSwap if ((colSwap % 2) == 1) colSwap = n - colSwap; // Check if rows required to // be corrected is odd and then // assign N-rowSwap to rowSwap if ((rowSwap % 2) == 1) rowSwap = n - rowSwap; } else { // Take min of colSwap and N-colSwap colSwap = Math.Min(colSwap, n - colSwap); // Take min of rowSwap and N-rowSwap rowSwap = Math.Min(rowSwap, n - rowSwap); } // Finally return answer return (rowSwap + colSwap) / 2; } // Driver Code public static void Main(String[] args) { // Given matrix int[,] M = { { 0, 1, 1, 0 }, { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1 } }; // Function Call int ans = minSwaps(M); // Print answer Console.WriteLine(ans); } } // This code is contributed by gauravrajput1
Javascript
<script> // javascript program for the above approach // Function to return number of moves // to convert matrix into chessboard function minSwaps(b) { // Size of the matrix var n = b.length; // Traverse the matrix for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if ((b[0][0] ^ b[0][j] ^ b[i][0] ^ b[i][j]) == 1) { return -1; } } } // Initialize rowSum to count 1s in row var rowSum = 0; // Initialize colSum to count 1s in column var colSum = 0; // To store no. of rows to be corrected var rowSwap = 0; // To store no. of columns to be corrected var colSwap = 0; // Traverse in the range [0, N-1] for (i = 0; i < n; i++) { rowSum += b[i][0]; colSum += b[0][i]; var cond1 = 0; var cond2 = 0; if(b[i][0] == i % 2) cond1 = 1; if(b[0][i] == i % 2) cond2 = 1; rowSwap += cond1; colSwap += cond2; } // Check if rows is either N/2 or // (N+1)/2 and return -1 if (rowSum != n / 2 && rowSum != (n + 1) / 2) return -1; // Check if rows is either N/2 // or (N+1)/2 and return -1 if (colSum != n / 2 && colSum != (n + 1) / 2) return -1; // Check if N is odd if (n % 2 == 1) { // Check if column required to be // corrected is odd and then // assign N-colSwap to colSwap if ((colSwap % 2) == 1) colSwap = n - colSwap; // Check if rows required to // be corrected is odd and then // assign N-rowSwap to rowSwap if ((rowSwap % 2) == 1) rowSwap = n - rowSwap; } else { // Take min of colSwap and N-colSwap colSwap = Math.min(colSwap, n - colSwap); // Take min of rowSwap and N-rowSwap rowSwap = Math.min(rowSwap, n - rowSwap); } // Finally return answer return (rowSwap + colSwap) / 2; } // Driver Code var M = [[ 0, 1, 1, 0 ], [ 0, 1, 1, 0 ], [ 1, 0, 0, 1 ], [ 1, 0, 0, 1 ] ]; // Function Call var ans = minSwaps(M); // Print answer document.write(ans); // This code contributed by Princi Singh </script>
2
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA