#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e3+7;
vector<pair<char,pair<int,char>>>ans;
int odwr[LIM], odwk[LIM], iler[LIM][26], ilek[LIM][26], n, m;
queue<pair<int,int>>q;
string T[LIM];
void checkr(int x) {
if(odwr[x]) return;
int ile=0;
rep(i, 26) if(iler[x][i]) ++ile;
if(ile>1) return;
q.push({0, x});
odwr[x]=1;
rep(i, 26) if(iler[x][i]) ans.pb({'R', {x+1, 'A'+i}});
if(ile==0) ans.pb({'R', {x+1, 'A'}});
}
void checkk(int x) {
if(odwk[x]) return;
int ile=0;
rep(i, 26) if(ilek[x][i]) ++ile;
if(ile>1) return;
q.push({1, x});
odwk[x]=1;
rep(i, 26) if(ilek[x][i]) ans.pb({'K', {x+1, 'A'+i}});
if(ile==0) ans.pb({'K', {x+1, 'A'}});
}
void usun(int a, int b) {
if(T[a][b]=='?') return;
--iler[a][T[a][b]-'A'];
--ilek[b][T[a][b]-'A'];
T[a][b]='?';
checkr(a);
checkk(b);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
rep(i, n) {
cin >> T[i];
rep(j, m) {
++iler[i][T[i][j]-'A'];
++ilek[j][T[i][j]-'A'];
}
}
rep(i, n) checkr(i);
rep(i, m) checkk(i);
while(!q.empty()) {
int a=q.front().st, b=q.front().nd; q.pop();
if(a==0) rep(i, m) usun(b, i);
else rep(i, n) usun(i, b);
}
reverse(all(ans));
cout << ans.size() << '\n';
for(auto i : ans) cout << i.st << " " << i.nd.st << " " << i.nd.nd << '\n';
}
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 | #include<bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int LIM=2e3+7; vector<pair<char,pair<int,char>>>ans; int odwr[LIM], odwk[LIM], iler[LIM][26], ilek[LIM][26], n, m; queue<pair<int,int>>q; string T[LIM]; void checkr(int x) { if(odwr[x]) return; int ile=0; rep(i, 26) if(iler[x][i]) ++ile; if(ile>1) return; q.push({0, x}); odwr[x]=1; rep(i, 26) if(iler[x][i]) ans.pb({'R', {x+1, 'A'+i}}); if(ile==0) ans.pb({'R', {x+1, 'A'}}); } void checkk(int x) { if(odwk[x]) return; int ile=0; rep(i, 26) if(ilek[x][i]) ++ile; if(ile>1) return; q.push({1, x}); odwk[x]=1; rep(i, 26) if(ilek[x][i]) ans.pb({'K', {x+1, 'A'+i}}); if(ile==0) ans.pb({'K', {x+1, 'A'}}); } void usun(int a, int b) { if(T[a][b]=='?') return; --iler[a][T[a][b]-'A']; --ilek[b][T[a][b]-'A']; T[a][b]='?'; checkr(a); checkk(b); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; rep(i, n) { cin >> T[i]; rep(j, m) { ++iler[i][T[i][j]-'A']; ++ilek[j][T[i][j]-'A']; } } rep(i, n) checkr(i); rep(i, m) checkk(i); while(!q.empty()) { int a=q.front().st, b=q.front().nd; q.pop(); if(a==0) rep(i, m) usun(b, i); else rep(i, n) usun(i, b); } reverse(all(ans)); cout << ans.size() << '\n'; for(auto i : ans) cout << i.st << " " << i.nd.st << " " << i.nd.nd << '\n'; } |
English