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

using namespace std;

int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int>> p(n,vector<int> (m));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            char x;
            cin>>x;
            p[i][j]=x-'A';
        }
    vector<vector<int>> r(n,vector<int> (26,0));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            r[i][p[i][j]]++;
    vector<vector<int>> c(m,vector<int> (26,0));
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
            c[i][p[j][i]]++;
    vector<int> rl(n);
    vector<int> cl(m);
    vector<bool> rb(n,0);
    vector<bool> cb(m,0);
    queue<pair<pair<char,int>,char>> q;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<26;j++)
            if(r[i][j]>0) rl[i]++;
        if(rl[i]==1) {q.push({{'R',i},'A'+p[i][0]});rb[i]=true;}
    }
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<26;j++)
            if(c[i][j]>0) cl[i]++;
        if(cl[i]==1) {q.push({{'K',i},'A'+p[0][i]});cb[i]=true;}
    }
    int rcnt=0,ccnt=0;
    queue<int> qr,qc;
    for(int i=0;i<n;i++) qr.push(i);
    for(int i=0;i<m;i++) qc.push(i);
    vector<pair<pair<char,int>,char>> ans;
    while(rcnt!=n && ccnt!=m)
    {
        auto a=q.front();
        q.pop();
        ans.push_back(a);
        int i=a.first.second;
        if(a.first.first=='R')
        {
            rcnt++;
            for(int j=0;j<m;j++)
            {
                if(cb[j]==true) continue;
                c[j][p[i][j]]--;
                if(c[j][p[i][j]]==0) cl[j]--;
                if(cl[j]==1)
                {
                    for(int k=0;k<26;k++)
                    {
                        if(c[j][k]>0)
                        {
                            q.push({{'K',j},'A'+k});
                            cb[j]=true;
                        }
                    }
                }
            }
        }
        else
        {
            ccnt++;
            for(int j=0;j<n;j++)
            {
                if(rb[j]==true) continue;
                r[j][p[j][i]]--;
                if(r[j][p[j][i]]==0) rl[j]--;
                if(rl[j]==1)
                {
                    for(int k=0;k<26;k++)
                    {
                        if(r[j][k]>0)
                        {
                            q.push({{'R',j},'A'+k});
                            rb[j]=true;
                        }
                    }
                }
            }
        }
    }
    cout<<ans.size()<<endl;
    for(int i=ans.size()-1;i>=0;i--) cout<<ans[i].first.first<<" "<<ans[i].first.second+1<<" "<<ans[i].second<<endl;
}