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
/*
Wybierze on sobie docelową kolorową planszę o wymiarach n×m, a grę rozpocznie z planszą n×m, na
której żadne pole nie ma koloru. W jednym ruchu może on wybrać rząd lub kolumnę i przemalować wszystkie
pola w nim/niej wybranym przez siebie kolorem (zwróć uwagę na to, że daje mu to większą swobodę
niż w grze przedstawionej na obrazkach powyżej, gdzie wiersze i kolumny miały narzucone kolory). Aby nieco
sformalizować zadanie, wszystkie kolory oznaczył wielkimi literami alfabetu angielskiego. Czy pomożesz mu i
napiszesz program, który dla każdej zadanej przez niego planszy poda ciąg ruchów, który poprawnie stworzy
docelowy układ kolorów? Możesz założyć, że dostaniesz dane wejściowe, w których ten cel można osiągnąć w
co najwyżej n + m ruchach
*/
#include <bits/stdc++.h>
using namespace std;

int n, m;
char a[2001][2001];

queue<pair<bool, int>> ready;

int cntH[2001][200], cntV[2001][200];
bool usedH[2001], usedV[2001];

int checkV(int x){
    //cout << "checkV " << x << "\n";

    int cnt = 0;
    int clr = 0;
    for(int i = 'A'; i <= 'Z'; i++){
        if(cntV[x][i] > 0){
            cnt++;
            clr = i;
        }
    }
    if(cnt == 1){
        return clr;
    }
    return 0;
}

int checkH(int x){
    //cout << "checkH " << x << "\n";

    int cnt = 0;
    int clr = 0;
    for(int i = 'A'; i <= 'Z'; i++){
        if(cntH[x][i] > 0){
            cnt++;
            clr = i;
        }
    }
    if(cnt == 1){
        return clr;
    }
    return 0;
}

stack<pair<bool, pair<int, char>>> res;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
            cntH[i][a[i][j]]++;
            cntV[j][a[i][j]]++;
        }
    }

    for(int i = 0; i < n; i++){
        int clr = checkH(i);
        if(clr != 0){
            //cout << "row " << i + 1 << " " << (char)clr << " is ready\n";
            ready.push({0, i});
            usedH[i] = 1;
        }
    }

    for(int i = 0; i < m; i++){
        int clr = checkV(i);
        if(clr != 0){
            //cout << "col " << i + 1 << " " << (char)clr << " is ready\n";
            ready.push({1, i});
            usedV[i] = 1;
        }
    }

    while(!ready.empty()){
        pair<bool, int> p = ready.front();
        ready.pop();
        if(p.first == 0){
            int clr = checkH(p.second);
            if(clr != 0){
                res.push({0, {p.second, clr}});
                for(int i = 0; i < m; i++){
                    if(usedV[i]){
                        continue;
                    }

                    cntV[i][a[p.second][i]]--;
                    if(cntV[i][a[p.second][i]] == 0){
                        int clr2 = checkV(i);
                        if(clr2 != 0){
                            ready.push({1, i});
                            usedV[i] = 1;
                        }
                    }
                }
            }
        }
        else{
            int clr = checkV(p.second);
            if(clr != 0){
                res.push({1, {p.second, clr}});
                for(int i = 0; i < n; i++){
                    if(usedH[i]){
                        continue;
                    }

                    cntH[i][a[i][p.second]]--;
                    if(cntH[i][a[i][p.second]] == 0){
                        int clr2 = checkH(i);
                        if(clr2 != 0){
                            ready.push({0, i});
                            usedH[i] = 1;
                        }
                    }
                }
            }
        }
    }

    cout << res.size() << "\n";
    while(!res.empty()){
        pair<bool, pair<int, char>> p = res.top();
        res.pop();
        if(p.first == 0){
            cout << "R " << p.second.first + 1 << " " << p.second.second << "\n";
        }
        else{
            cout << "K " << p.second.first + 1 << " " << p.second.second << "\n";
        }
    }
}