Hiitism

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

int rs, cs;
int m[1000][1000];
int row_counts[1000][4];
int col_counts[1000][4];
bool removed_rows[1000];
bool removed_cols[1000];
int total_count;
vector<string> operations{};

int char_to_int(char c) {
    switch (c) {
        case '.': return 0;
        case 'H': return 1;
        case 'I': return 2;
        case 'T': return 3;
        default: return -1;
    }
}

char int_to_char(int c) {
    switch (c) {
        case 0: return '.';
        case 1: return 'H';
        case 2: return 'I';
        case 3: return 'T';
        default: return '?';
    }
}

void init_painting() {
    cin >> rs >> cs;
    char c;
    for (int i = 0; i < rs; ++i) {
        for (int j = 0; j < cs; ++j) {
            cin >> c;
            m[i][j] = char_to_int(c);
        }
    }
}

void init_counts() {
    for (int i = 0; i < rs; ++i) {
        for (int j = 0; j < cs; ++j) {
            ++row_counts[i][m[i][j]];
            ++col_counts[j][m[i][j]];
            if (m[i][j]) {
                ++total_count;
            }
        }
    }
}

void remove_row(int r, int c) {
    operations.push_back("R " + to_string(r+1) + " " + int_to_char(c));
    removed_rows[r] = true;
    for (int j = 0; j < cs; ++j) {
        if (removed_cols[j]) continue;
        --col_counts[j][c];
        --total_count;
    }
}

void remove_col(int col, int c) {
    operations.push_back("C " + to_string(col+1) + " " + int_to_char(c));
    removed_cols[col] = true;
    for (int i = 0; i < rs; ++i) {
        if (removed_rows[i]) continue;
        --row_counts[i][c];
        --total_count;
    }
}

void remove_rows() {
    for (int i = 0; i < rs; ++i) {
        if (row_counts[i][0]) continue;
        if (removed_rows[i]) continue;
        if (row_counts[i][1] == 0 && row_counts[i][2] == 0) {
            remove_row(i, 3);
        }
        if (row_counts[i][1] == 0 && row_counts[i][3] == 0) {
            remove_row(i, 2);
        }
        if (row_counts[i][2] == 0 && row_counts[i][3] == 0) {
            remove_row(i, 1);
        }
    }
}

void remove_cols() {
    for (int j = 0; j < cs; ++j) {
        if (col_counts[j][0]) continue;
        if (removed_cols[j]) continue;
        if (col_counts[j][1] == 0 && col_counts[j][2] == 0) {
            remove_col(j, 3);
        }
        if (col_counts[j][1] == 0 && col_counts[j][3] == 0) {
            remove_col(j, 2);
        }
        if (col_counts[j][2] == 0 && col_counts[j][3] == 0) {
            remove_col(j, 1);
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    init_painting();
    init_counts();

    int prev_total_count = -1;
    while (total_count) {
        prev_total_count = total_count;
        remove_rows();
        remove_cols();
        if (!total_count) break;
        if (total_count == prev_total_count) {
            cout << "Impossible" << endl;
            return 0;
        }
    }
    cout << operations.size() << endl;
    for (auto it = operations.rbegin(); it != operations.rend(); ++it) {
        cout << *it << endl;
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED