Polihroniade

#include <bits/stdc++.h>
#define Nmax 1002
using namespace std;

int N, T, P, ans;
int SL[Nmax], SC[Nmax], cnt1, cnt2;
bool mat[Nmax][Nmax], ok[Nmax];
vector<int> lin[2], col[2];

void Preprocess()
{
    for (int i = 0; i < 2; ++i)
        lin[i].clear(), col[i].clear();
    for (int i = 1; i <= N; ++i)
        SL[i] = SC[i] = 0, ok[i] = 0;

    cnt1 = cnt2 = 1;
    ans = 0;
}

bool check()
{
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            if (mat[i][j])
                ++SL[i], ++SC[j];

    for (int i = 1; i <= N; ++i)
        if (SL[i] != N / 2 || SC[i] != N / 2)
            return 0;

    for (int i = 2; i <= N; ++i)
    {
        bool k = 1;
        for (int j = 1; j <= N; ++j)
            if (mat[i][j] != mat[1][j])
                k = 0;
        if (k)
            ++cnt1;
    }

    for (int j = 2; j <= N; ++j)
    {
        bool k = 1;
        for (int i = 1; i <= N; ++i)
            if (mat[i][j] != mat[i][1])
                k = 0;
        if (k)
            ++cnt2;
    }

    if (cnt1 != N / 2 || cnt2 != N / 2)
        return 0;
    return 1;
}

void solve(vector<int> v[2], bool x)
{
    ok[1] = 1;
    int cnt = 0;

    for (int i = 2; i <= N; ++i)
    {
        if (x == 0)
        {
            if (mat[i][1] == mat[1][1])
                ok[i] = 1;
            else
                ok[i] = 0;
        }
        else
        {
            if (mat[1][i] == mat[1][1])
                ok[i] = 1;
            else
                ok[i] = 0;
        }
        if (ok[i] != i % 2)
            ++cnt;
    }

    for (int i = 1; i <= N; ++i)
    {
        if (cnt <= N / 2)
            if (ok[i] != i % 2)
                v[ok[i]].push_back(i);
        if (cnt > N / 2)
            if ((ok[i] ^ 1) != i % 2)
                v[ok[i]].push_back(i);
    }

    ans += min(cnt, N - cnt);
}
int main()
{
    cin >> P >> T;
    while(T--)
    {
        cin >> N;
        Preprocess();
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
            {
                char ch;
                cin >> ch;
                mat[i][j] = ch - '0';
            }

        if(P == 1)
            cout << check() << '\n';
        else
        {
            solve(lin, 0);
            solve(col, 1);
            cout << ans / 2 << '\n';
            if (P == 3)
            {

                for(int i = 0; i < (int)lin[0].size(); ++i)
                    cout << "L " << lin[0][i] << " " << lin[1][i] << '\n';
                for (int i = 0; i < (int)col[0].size(); ++i)
                    cout << "C " << col[0][i] << " " << col[1][i] << '\n';
            }
        }
    }

    return 0;
}