Intercambios mínimos para construir un tablero de ajedrez válido

Dada una array de tamaño N * N que contiene solo 0 y 1, donde 0 representa el blanco y 1 representa el negro. La tarea es minimizar el número de intercambios para formar un tablero de ajedrez válido. Solo se pueden intercambiar 2 filas o 2 columnas entre sí.
Si es imposible formar un tablero de ajedrez, devuelve -1.

Ejemplos:

Entrada: {{0, 1, 1, 0}, {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 0, 0, 1}}
Salida: 2
Explicación: Un potencial La secuencia de movimientos se muestra a continuación.  
El primer movimiento intercambia la primera y la segunda columna.
El segundo movimiento intercambia la segunda y la tercera fila.

Entrada: {{0, 1, 0}, {1, 0, 1}, {1, 1, 0}}
Salida: -1

Enfoque: El problema se puede resolver con base en las siguientes propiedades del tablero de ajedrez y la observación:

Propiedades del tablero de ajedrez:

1. En un tablero de ajedrez válido, hay 2 y solo 2 tipos de filas y una es inversa a la otra, lo mismo ocurre con las columnas.
   Un corolario es que cualquier rectángulo dentro del tablero con esquinas arriba a la izquierda, arriba a la derecha, abajo a la izquierda y abajo a la derecha debe tener 4 ceros o 2 unos y 2 ceros o 4 ceros.
2. Otra propiedad importante es que cada fila y columna tiene mitades. Supongamos que el tablero es N * N:
   • Si N = 2 * K, cada fila y cada columna tiene K unos y K ceros.
   • Si N = 2 * K + 1, cada fila y cada columna tiene K unos y K + 1 ceros o K + 1 unos y K ceros.

Dado que el proceso de intercambio no rompe estas propiedades, para que un tablero determinado sea válido, estas propiedades deben cumplirse.
Estas dos condiciones son condiciones necesarias y suficientes para un tablero de ajedrez válido .

Recuento de intercambio:

Para calcular la cantidad de intercambios necesarios para crear el tablero de ajedrez, iterar sobre la primera fila y la primera columna y verificar si hay blancos y negros alternativos. 

Siga los pasos mencionados a continuación para implementar la idea:

• Inicialmente se verifica si el tablero es válido o no usando las propiedades del tablero, si el tablero es válido se procede de lo contrario se devuelve -1.
• Itere sobre la primera fila y la primera columna y cuente la cantidad de 1 en ambas y también cuente la cantidad de intercambios requeridos usando la condición, A[i] = i%2 .
• Use el número de unos calculado para verificar la segunda propiedad del tablero de ajedrez (es decir, cada fila y columna tiene la mitad de unos), si el tablero no es válido, devuelva -1; de lo contrario, continúe. 
• Ahora bien, si N es par, entonces los intercambios mínimos se almacenan como están.
• Si N es impar, entonces tomamos los intercambios pares, ya que solo podemos intercambiar 2 filas o 2 columnas.

A continuación se muestra la implementación del enfoque anterior.

// C++ code to implement the approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to return minimum swaps
int movesToChessboard(vector<vector<int> >& board)
{
    int n = board.size();
  
    // Loop to check whether the board
    // can be made valid or not
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (board[0][0] ^ board[r][0] ^ board[0]
                ^ board[r] == 1) {
                return -1;
            }
        }
    }
  
    int rowsum = 0;
    int colsum = 0;
    int rowswap = 0;
    int colswap = 0;
  
    // Loop to calculate sum and swap
    for (int i = 0; i < n; i++) {
        rowsum += board[i][0];
        colsum += board[0][i];
        rowswap += board[i][0] == i % 2;
        colswap += board[0][i] == i % 2;
    }
  
    // If there are more white or more black
    if (rowsum != n / 2 and rowsum != (n + 1) / 2)
        return -1;
    if (colsum != n / 2 and colsum != (n + 1) / 2)
        return -1;
  
    // If n is odd
    if (n % 2) {
        if (rowswap % 2)
            rowswap = n - rowswap;
        if (colswap % 2)
            colswap = n - colswap;
    }
  
    // If n is even
    else {
        rowswap = min(rowswap, n - rowswap);
        colswap = min(colswap, n - colswap);
    }
  
    // Return the ans
    return (rowswap + colswap) / 2;
}
  
// Driver Code
int main()
{
    // Given vector array
    vector<vector<int> > arr{ { 0, 1, 1, 0 },
                              { 0, 1, 1, 0 },
                              { 1, 0, 0, 1 },
                              { 1, 0, 0, 1 } };
  
    // Function call
    int minswap = movesToChessboard(arr);
  
    // Printing the output
    if (minswap == -1)
        cout << "Impossible";
    else
        cout << minswap << endl;
    return 0;
}

2

Complejidad temporal: O(N ² ) 
Espacio auxiliar: O(1)