#include <algorithm> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <string> #include <vector> using namespace std; #define PB push_back #define MP make_pair #define F first #define S second #define ALL(x) (x).begin(),(x).end() #define SIZE(x) (int)(x).size() #define CLEAR(tab) memset(tab, 0, sizeof(tab)) #define REP(x, n) for(int x = 0; x < (n); x++) #define FOR(x, b, e) for(int x = (b); x <= (e); x++) #define FORD(x, b, e) for(int x = (b); x >= (e); x--) #define VAR(v, n) __typeof(n) v = (n) #define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define DEBUG(fmt, ...) fprintf(stderr, fmt, ##__VA_ARGS__) typedef long long int LL; typedef pair<int,int> PII; typedef vector<int> VI; const int MXN = 4040; const int C = 262144; const int INF = 1000000001; const int MOD = 1000000007; int n, m; int cntA[MXN][30], cntB[MXN][30]; char str[MXN][MXN]; pair<char, pair<int, char> > res[MXN]; int ss; void test() { scanf("%d %d\n", &n, &m); FOR(i, 1, n) { FOR(j, 1, m) { char c; while(1) { c = getchar(); if(isalpha(c)) break; } str[i][j] = c; } FOR(j, 1, m) { cntA[i][str[i][j] - 'A']++; cntB[j][str[i][j] - 'A']++; } } FOR(i, 1, n + m) { bool dec = 0; FOR(j, 1, n) { int count = 0; int ind = 0; FOR(k, 0, 'Z' - 'A') if(cntA[j][k] > 0) { count++; ind = k; } if(count == 1) { res[ss++] = MP('R', MP(j, ind + 'A')); cntA[j][ind] = 0; FOR(k, 1, m) cntB[k][ind]--; dec = 1; break; } } if(dec) continue; FOR(j, 1, m) { int count = 0; int ind = 0; FOR(k, 0, 'Z' - 'A') if(cntB[j][k] > 0) { count++; ind = k; } if(count == 1) { res[ss++] = MP('K', MP(j, ind + 'A')); cntB[j][ind] = 0; FOR(k, 1, n) cntA[k][ind]--; dec = 1; break; } } if(!dec) break; } printf("%d\n", ss); FORD(i, ss - 1, 0) printf("%c %d %c\n", res[i].F, res[i].S.F, res[i].S.S); } int main() { int te = 1; // scanf("%d", &te); while(te--) test(); 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 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 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | #include <algorithm> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <string> #include <vector> using namespace std; #define PB push_back #define MP make_pair #define F first #define S second #define ALL(x) (x).begin(),(x).end() #define SIZE(x) (int)(x).size() #define CLEAR(tab) memset(tab, 0, sizeof(tab)) #define REP(x, n) for(int x = 0; x < (n); x++) #define FOR(x, b, e) for(int x = (b); x <= (e); x++) #define FORD(x, b, e) for(int x = (b); x >= (e); x--) #define VAR(v, n) __typeof(n) v = (n) #define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define DEBUG(fmt, ...) fprintf(stderr, fmt, ##__VA_ARGS__) typedef long long int LL; typedef pair<int,int> PII; typedef vector<int> VI; const int MXN = 4040; const int C = 262144; const int INF = 1000000001; const int MOD = 1000000007; int n, m; int cntA[MXN][30], cntB[MXN][30]; char str[MXN][MXN]; pair<char, pair<int, char> > res[MXN]; int ss; void test() { scanf("%d %d\n", &n, &m); FOR(i, 1, n) { FOR(j, 1, m) { char c; while(1) { c = getchar(); if(isalpha(c)) break; } str[i][j] = c; } FOR(j, 1, m) { cntA[i][str[i][j] - 'A']++; cntB[j][str[i][j] - 'A']++; } } FOR(i, 1, n + m) { bool dec = 0; FOR(j, 1, n) { int count = 0; int ind = 0; FOR(k, 0, 'Z' - 'A') if(cntA[j][k] > 0) { count++; ind = k; } if(count == 1) { res[ss++] = MP('R', MP(j, ind + 'A')); cntA[j][ind] = 0; FOR(k, 1, m) cntB[k][ind]--; dec = 1; break; } } if(dec) continue; FOR(j, 1, m) { int count = 0; int ind = 0; FOR(k, 0, 'Z' - 'A') if(cntB[j][k] > 0) { count++; ind = k; } if(count == 1) { res[ss++] = MP('K', MP(j, ind + 'A')); cntB[j][ind] = 0; FOR(k, 1, n) cntA[k][ind]--; dec = 1; break; } } if(!dec) break; } printf("%d\n", ss); FORD(i, ss - 1, 0) printf("%c %d %c\n", res[i].F, res[i].S.F, res[i].S.S); } int main() { int te = 1; // scanf("%d", &te); while(te--) test(); return 0; } |