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
#include<bits/stdc++.h>

using namespace std;

struct ruch{bool r; int i; char c;};

void update(int i, char c, queue<ruch> &Q, set<int> &U, vector<vector<int>> &R, vector<int> &K, vector<vector<char>> &A, bool b)
{
    U.erase(i);
    for(int j=0; j<R.size(); j++)
    {
        R[j][c-65]--;
        if(R[j][c-65] == 0)
        {
            K[j]--;
            if(K[j] == 1)
            {
                int x = *U.begin();
                char k;
                if(b) k = A[x][j];
                else k = A[j][x];
                Q.push({!b, j, k});
            }
        }
    }
}

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

    int n, m;
    cin >> n >> m;
    vector<int> rn(n), cn(m);
    set<int> NC, NR;
    vector<vector<int>> R(n, vector<int>(26)), C(m, vector<int>(26));
    vector<vector<char>> A(n, vector<char>(m));
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            char a;
            cin >> a;
            if(R[i][a-65] == 0) rn[i]++;
            if(C[j][a-65] == 0) cn[j]++;
            R[i][a-65]++;
            C[j][a-65]++;
            A[i][j] = a;
        }
    }

    //for(int i=0; i<m; i++) cerr << cn[i] << " ";
    //cerr << "\n";

    stack<ruch> S;
    queue<ruch> Q;
    for(int i=0; i<n; i++)
    {
        NR.insert(i);
        if(rn[i] == 1) Q.push({true, i, A[i][0]});
    }
    for(int i=0; i<m; i++)
    {
        NC.insert(i);
        if(cn[i] == 1) Q.push({false, i, A[0][i]});
    }

    while(!Q.empty())
    {
        bool b = Q.front().r;
        int i = Q.front().i;
        char c = Q.front().c;
        S.push(Q.front());
        Q.pop();

        if(b) update(i, c, Q, NR, C, cn, A, b);
        else update(i, c, Q, NC, R, rn, A, b);
    }

    cout << S.size() << "\n";
    while(!S.empty())
    {
        if(S.top().r) cout << "R ";
        else cout << "K ";
        cout << S.top().i+1 << " " << S.top().c << "\n";
        S.pop();
    }
}