1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>
#include <queue>
#include <vector>

struct data {
    int id;
    bool is_col;
    char znak;
    std::vector<short> is_before;
};

short color[2][26][2001];
short unique[2][2001];

std::vector<data> d;
std::vector<int> ordered;

int n, m;

char tab[2001][2001];

bool v_row[2001], v_col[2001], row1[2001], col1[2001];

short r_id[2001], c_id[2001];

short level[4000];
std::queue<short> lv;
std::queue<std::pair<std::pair<bool, short>, char>> q1;

void row(int x, char znak);
void col(int x, char znak);

int main()
{
    std::ios_base::sync_with_stdio();
    std::cin.tie();

    std::cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            std::cin >> tab[i][j];
            if (!color[0][tab[i][j] - 'A'][i])
                unique[0][i]++;
            color[0][tab[i][j] - 'A'][i]++;
            if (!color[1][tab[i][j] - 'A'][j])
                unique[1][j]++;
            color[1][tab[i][j] - 'A'][j]++;
        }

    for (int i = 1; i <= n; i++)
        if (unique[0][i] == 1) {
            q1.push({ { 0, i }, tab[i][1] });
            row1[i] = true;
        }

    for (int i = 1; i <= m; i++)
        if (unique[1][i] == 1) {
            q1.push({ { 1, i }, tab[1][i] });
            col1[i] = true;
        }

    while (!q1.empty()) {
        if (q1.front().first.first) {
            if (!v_col[q1.front().first.second])
                col(q1.front().first.second, q1.front().second);
        }
        else if (!v_row[q1.front().first.second])
            row(q1.front().first.second, q1.front().second);
        q1.pop();
    }

    for (int i = 0; i < d.size(); i++)
        if (!level[i])
            lv.push(i);
    while (!lv.empty()) {
        for (auto element : d[lv.front()].is_before) {
            level[element]--;
            if (!level[element])
                lv.push(element);
        }
        ordered.push_back(lv.front());
        lv.pop();
    }

    std::cout << d.size();

    for (int i = 0; i < ordered.size(); i++) {
        if (d[ordered[i]].is_col)
            std::cout << "\nK ";
        else
            std::cout << "\nR ";
        std::cout << d[ordered[i]].id << ' ' << d[ordered[i]].znak;
    }

}

void row(int x, char znak) {
    r_id[x] = d.size();
    d.push_back({ x, 0, znak });
    v_row[x] = true;
    for (int i = 1; i <= m; i++) {
        if (tab[x][i] != znak) {
            if (!v_col[i])
                col(i, tab[x][i]);
            d[r_id[x]].is_before.push_back(c_id[i]);
            level[c_id[i]]++;
        }
        else {
            color[1][tab[x][i] - 'A'][i]--;
            if (!color[1][tab[x][i] - 'A'][i])
                unique[1][i]--;
            if (unique[1][i] == 1 && !col1[i]) {
                for (int j = 0; j < 26; j++)
                    if (color[1][j][i]) {
                        q1.push({ {1, i }, static_cast<char>('A' + j) });
                        col1[i] = true;
                        break;
                    }
            }
        }
    }
}

void col(int x, char znak) {
    c_id[x] = d.size();
    d.push_back({ x, 1, znak });
    v_col[x] = true;
    for (int i = 1; i <= n; i++) {
        if (tab[i][x] != znak) {
            if (!v_row[i])
                row(i, tab[i][x]);
            d[c_id[x]].is_before.push_back(r_id[i]);
            level[r_id[i]]++;
        }
        else {
            color[0][tab[i][x] - 'A'][i]--;
            if (!color[0][tab[i][x] - 'A'][i])
                unique[0][i]--;
            if (unique[0][i] == 1 && !row1[i]) {
                for (int j = 0; j < 26; j++)
                    if (color[0][j][i]) {
                        q1.push({ {0, i }, static_cast<char>('A' + j) });
                        row1[i] = true;
                        break;
                    }
            }
        }
    }
}