#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'; } |