#include <bits/stdc++.h> using namespace std; const int MX=4004; pair<int,int> ans[MX]; int n,m,num,q[MX],cr[MX][28],ck[MX][28],dr[MX],dk[MX]; bool ur[MX],uk[MX],wr[MX],wk[MX]; char s[MX]; int main() { scanf("%d%d",&n,&m); for (int i=1; i<=n; i++) { scanf("%s",s+1); for (int j=1; j<=m; j++) { s[j]-='A'; if (++cr[i][s[j]]==1) ++dr[i]; if (++ck[j][s[j]]==1) ++dk[j]; } } int fi=0,fr=0; for (int i=1; i<=n; i++) if (dr[i]==1) { ur[i]=true; q[fr++]=i; } for (int i=1; i<=m; i++) if (dk[i]==1) { uk[i]=true; q[fr++]=n+i; } while (fi<fr) { int i=q[fi++]; ans[++num].first=i; if (i>n) { i-=n; wk[i]=true; int ch; for (ch=0; ch<26; ch++) if (ck[i][ch]) { ans[num].second=ch; break; } if (ch>=26) { --num; continue; } for (int j=1; j<=n; j++) if (!wr[j]) if (--cr[j][ans[num].second]==0) if (--dr[j]==1 && !ur[j]) { ur[j]=true; q[fr++]=j; } } else { wr[i]=true; int ch; for (ch=0; ch<26; ch++) if (cr[i][ch]) { ans[num].second=ch; break; } if (ch>=26) { --num; continue; } for (int j=1; j<=m; j++) if (!wk[j]) if (--ck[j][ans[num].second]==0) if (--dk[j]==1 && !uk[j]) { uk[j]=true; q[fr++]=n+j; } } } printf("%d\n",num); for (int i=num; i>0; i--) if (ans[i].first>n) printf("K %d %c\n",ans[i].first-n,'A'+ans[i].second); else printf("R %d %c\n",ans[i].first,'A'+ans[i].second); return 0; }
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 | #include <bits/stdc++.h> using namespace std; const int MX=4004; pair<int,int> ans[MX]; int n,m,num,q[MX],cr[MX][28],ck[MX][28],dr[MX],dk[MX]; bool ur[MX],uk[MX],wr[MX],wk[MX]; char s[MX]; int main() { scanf("%d%d",&n,&m); for (int i=1; i<=n; i++) { scanf("%s",s+1); for (int j=1; j<=m; j++) { s[j]-='A'; if (++cr[i][s[j]]==1) ++dr[i]; if (++ck[j][s[j]]==1) ++dk[j]; } } int fi=0,fr=0; for (int i=1; i<=n; i++) if (dr[i]==1) { ur[i]=true; q[fr++]=i; } for (int i=1; i<=m; i++) if (dk[i]==1) { uk[i]=true; q[fr++]=n+i; } while (fi<fr) { int i=q[fi++]; ans[++num].first=i; if (i>n) { i-=n; wk[i]=true; int ch; for (ch=0; ch<26; ch++) if (ck[i][ch]) { ans[num].second=ch; break; } if (ch>=26) { --num; continue; } for (int j=1; j<=n; j++) if (!wr[j]) if (--cr[j][ans[num].second]==0) if (--dr[j]==1 && !ur[j]) { ur[j]=true; q[fr++]=j; } } else { wr[i]=true; int ch; for (ch=0; ch<26; ch++) if (cr[i][ch]) { ans[num].second=ch; break; } if (ch>=26) { --num; continue; } for (int j=1; j<=m; j++) if (!wk[j]) if (--ck[j][ans[num].second]==0) if (--dk[j]==1 && !uk[j]) { uk[j]=true; q[fr++]=n+j; } } } printf("%d\n",num); for (int i=num; i>0; i--) if (ans[i].first>n) printf("K %d %c\n",ans[i].first-n,'A'+ans[i].second); else printf("R %d %c\n",ans[i].first,'A'+ans[i].second); return 0; } |