Polihroniade

#include <iostream>
#include <fstream>

using namespace std;

void getSolution(int p, int matrix[1000][1000], int n);
int isChessBoard(int mat[1000][1000], int n);
void canTransformToChessBoard(int matrix[1000][1000], int n);
void displayDetailedStepsForTransforming(int matrix[1000][1000], int n, int writeSteps);
int findNextLineToBeSwapped(int matrix[1000][1000], int n, int startingLine);
void swapRows(int mat[1000][1000], int n, int row1, int row2);
void swapColumns(int mat[1000][1000], int n, int col1, int col2);
int findNextColumnToBeSwapped(int matrix[1000][1000], int n, int startingCol);
void writeNumberOfStepsNeededToTransform(int matrix[1000][1000], int n);


ifstream fin("polihroniade.in");
ofstream fout("polihroniade.out", std::ios_base::trunc);

int main()
{
    int p, t;
    fin >> p >> t;
    int currentScenario = 1;
    while (currentScenario <= t)
    {
        int n;
        fin >> n;
        static int matrix[1000][1000] = {0};

        for (int i = 0; i < n; i++)
        {
            char line[n];
            fin >> line;
            for (int j = 0; j <  n; j++)
            {
                matrix[i][j] = line[j] - '0';
            }
        }
        getSolution(p, matrix, n);
        currentScenario++;
    }
    fout.close();
    fin.close();
    return 0;
}

void getSolution(int p, int matrix[1000][1000], int n) {
    switch (p) {
        case 1:
            canTransformToChessBoard(matrix, n);
            break;
        case 2:
            writeNumberOfStepsNeededToTransform(matrix, n);
            break;
        case 3:
            displayDetailedStepsForTransforming(matrix, n, 1);
            break;
        default:
            break;
    }
}

void canTransformToChessBoard(int matrix[1000][1000], int n) {
    int canBeTransformed = 1;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sum += matrix[i][j];
            if (matrix[0][0] ^ matrix[0][j] ^ matrix[i][0] ^ matrix[i][j]) {
                 canBeTransformed = 0; // can't be a chessboard
                break;
            }
        }
    }
    // To check the casses where matrix is filled only with 1s or 0s;
    if (sum == n * n || sum == 0) {
        fout << 0 << endl;
    } else {
        fout << canBeTransformed << endl;
    }
}



void displayDetailedStepsForTransforming(int matrix[1000][1000], int n, int writeStepsToFile) {
    if (isChessBoard(matrix, n)) {
        fout << 0 << endl;
    } else {
        // We do not check if the matrix can be or not chess because it is guaranteed by the problem
        // we call the prev function which knows to write the number of steps
        writeNumberOfStepsNeededToTransform(matrix, n);

        int rowSwap = 0, colSwap = 0;
        for (int i = 0; i < n; i++) {
            if (matrix[i][0] == i % 2) {
                rowSwap++;
                int lineToBeSwapped = findNextLineToBeSwapped(matrix, n, i);
                fout << "L " << i + 1 << " " << lineToBeSwapped + 1 << endl;
                swapRows(matrix, n, i, lineToBeSwapped);
            }
            if (matrix[0][i] == i % 2) {
                colSwap++;
                int colToBeSwapped = findNextColumnToBeSwapped(matrix, n, i);
                fout << "C " << i + 1 << " " << colToBeSwapped + 1 << endl;
                swapColumns(matrix, n, i, colToBeSwapped);
            }
        }
    }
}

void writeNumberOfStepsNeededToTransform(int matrix[1000][1000], int n) {
    // We do not check if the matrix can be or not chess because it is guaranteed by the problem
    int rowSwap = 0, colSwap = 0;
    for (int i = 0; i < n; i++) {

        if (matrix[i][0] == i % 2) {
            rowSwap++;
        }
        if (matrix[0][i] == i % 2) {
            colSwap++;
        }
    }
    colSwap = min(colSwap, n-colSwap);
    rowSwap = min(rowSwap, n - rowSwap);

    fout << (rowSwap + colSwap) / 2 << endl;
}

int isChessBoard(int mat[1000][1000], int n) {
    int isBoard = 1;
    for (int i = 0; i < n; i++)
    {
        if (isBoard == 0) break;
        for (int j = 0; j < n; j++)
        {
            // If it is the first line we do not check above and we take care of the margins
            if (i == 0)
            {
                // if it is the first column, we only check right and below neighbnors
                if (j == 0)
                {
                    if (mat[i][j] == mat[i+1][j] || mat[i][j] == mat[i][j+1])
                    {
                        isBoard = 0;
                        break;
                    }
                    // If it is the last column, we only check left and below neighbour
                }
                else if (j == n-1)
                {
                    if (mat[i][j] == mat[i+1][j] || mat[i][j] == mat[i][j-1])
                    {
                        isBoard = 0;
                        break;
                    }
                    // otherwise we check left, right and below neighbour
                }
                else
                {
                    if ( mat[i][j] == mat[i][j-1] || mat[i][j] == mat[i][j+1] || mat[i][j] == mat[i+1][j])
                    {
                        isBoard = 0;
                        break;
                    }
                }
            }
            else if (i == n-1)     // If it is the last line, we check above and take care of the margins
            {
                // If it is the first column, we only check above and right neighbours
                if (j == 0)
                {
                    if (mat[i][j] == mat[i-1][j] ||  mat[i][j] == mat[i][j+1])
                    {
                        isBoard = 0;
                        break;
                    }
                }
                else if (j == n -1 )     // if it is the last column we only check above and left neighbours {
                {
                    if (mat[i][j] == mat[i-1][j] || mat[i][j] == mat[i][j-1])
                    {
                        isBoard = 0;
                        break;
                    }
                }
                else     // otherwise we check above, left and right neighbours
                {
                    if (mat[i][j] ==  mat[i-1][j] || mat[i][j] == mat[i][j-1] || mat[i][j] == mat[i][j+1])
                    {
                        isBoard = 0;
                        break;
                    }
                }
            }
            else     // We are in the middle of the matrix and can check both above and below matrix but also left and right depending on the columns
            {
                if (j == 0)   // If it is the first column we check above, below and right neighbours
                {
                    if (mat[i][j] == mat[i-1][j] || mat[i][j] == mat[i+1][j] || mat[i][j] == mat[i][j+1])
                    {
                        isBoard = 0;
                        break;
                    }
                }
                else if (j == n - 1)     // If we are on the last column, we only check below, above and left neighbour
                {
                    if (mat[i][j] == mat[i-1][j] || mat[i][j] == mat[i+1][j] || mat[i][j] == mat[i][j-1])
                    {
                        isBoard = 0;
                        break;
                    }
                } else { // We can check all 4 neighbours: below, above, left and right
                    if (
                            mat[i][j] == mat[i-1][j] ||
                            mat[i][j] == mat[i+1][j] ||
                            mat[i][j] == mat[i][j-1]||
                            mat[i][j] == mat[i][j+1])
                    {
                        isBoard = 0;
                        break;
                    }
                }
            }
        }
    }
    return isBoard;
}

void swapRows(int mat[1000][1000], int n, int row1, int row2) {
    for (int i = 0; i < n; i++) {
        int temp = mat[row1][i];
        mat[row1][i] = mat[row2][i];
        mat[row2][i] = temp;
    }
}

void swapColumns(int mat[1000][1000], int n, int col1, int col2) {
    for (int i = 0; i < n; i++) {
        int temp = mat[i][col1];
        mat[i][col1] = mat[i][col2];
        mat[i][col2] = temp;
    }
}

int findNextLineToBeSwapped(int matrix[1000][1000], int n, int startingLine) {
    for (int i = startingLine+1; i < n; i++) {
        if (matrix[i][0] == i % 2) {
            return i;
        }
    }
    return -1;
}

int findNextColumnToBeSwapped(int matrix[1000][1000], int n, int startingCol) {
    for (int i = startingCol+1; i < n; i++) {
        if (matrix[0][i] == i % 2) {
            return i;
        }
    }
    return -1;
}