#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef pair<int, int> pii; #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 REP(x, n) for(int x = 0; x < (n); ++x) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define FOREACH(a, b) for (auto&a : (b)) #define PB push_back #define PF push_front #define MP make_pair #define ST first #define ND second #define DBG(vari) cerr<<#vari<<" = "<<(vari)<<endl; template <typename T> std::ostream& operator<<(std::ostream &output, const vector<T> &vec) { output << "["; FOREACH(x, vec) output << x << ", "; output << "]"; return output; } template <typename T, typename U> std::ostream& operator<<(std::ostream &output, const pair<T,U> &p) { output << "("; output << p.ST << ", " << p.ND; output << ")"; return output; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int H, W; cin >> H >> W; vector<string> S(H); REP(i, H) cin >> S[i]; vi r_ile_kol(H, 0); vi c_ile_kol(W, 0); int r_ile[H][300]; int c_ile[W][300]; REP(h, H) REP(i, 300) r_ile[h][i] = 0; REP(w, W) REP(i, 300) c_ile[w][i] = 0; REP(r, H) REP(c, W) { int d = S[r][c]; r_ile[r][d]++; if (r_ile[r][d] == 1) r_ile_kol[r]++; c_ile[c][d]++; if (c_ile[c][d] == 1) c_ile_kol[c]++; } vector<tuple<char, int, char>> res; while (1) { bool bylo = false; REP(i, H) if (r_ile_kol[i] == 1) { FOR(c, 'A', 'Z') if (r_ile[i][c] > 0) { res.emplace_back('R', i+1, c); r_ile_kol[i]=0; REP(j, W) { int d = S[i][j]; c_ile[j][d]--; if (c_ile[j][d] == 0) c_ile_kol[j]--; } } bylo=true; } REP(i, W) if (c_ile_kol[i] == 1) { FOR(c, 'A', 'Z') if (c_ile[i][c] > 0) { res.emplace_back('K', i+1, c); c_ile_kol[i]=0; REP(j, H) { int d = S[j][i]; r_ile[j][d]--; if (r_ile[j][d]==0) r_ile_kol[j]--; } } bylo=true; } if (!bylo) break; } reverse(ALL(res)); cout << SIZE(res) << endl; REP(i, SIZE(res)) { cout << get<0>(res[i]) << " " << get<1>(res[i]) << " " << get<2>(res[i]) << endl; } }
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 | #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef pair<int, int> pii; #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 REP(x, n) for(int x = 0; x < (n); ++x) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define FOREACH(a, b) for (auto&a : (b)) #define PB push_back #define PF push_front #define MP make_pair #define ST first #define ND second #define DBG(vari) cerr<<#vari<<" = "<<(vari)<<endl; template <typename T> std::ostream& operator<<(std::ostream &output, const vector<T> &vec) { output << "["; FOREACH(x, vec) output << x << ", "; output << "]"; return output; } template <typename T, typename U> std::ostream& operator<<(std::ostream &output, const pair<T,U> &p) { output << "("; output << p.ST << ", " << p.ND; output << ")"; return output; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int H, W; cin >> H >> W; vector<string> S(H); REP(i, H) cin >> S[i]; vi r_ile_kol(H, 0); vi c_ile_kol(W, 0); int r_ile[H][300]; int c_ile[W][300]; REP(h, H) REP(i, 300) r_ile[h][i] = 0; REP(w, W) REP(i, 300) c_ile[w][i] = 0; REP(r, H) REP(c, W) { int d = S[r][c]; r_ile[r][d]++; if (r_ile[r][d] == 1) r_ile_kol[r]++; c_ile[c][d]++; if (c_ile[c][d] == 1) c_ile_kol[c]++; } vector<tuple<char, int, char>> res; while (1) { bool bylo = false; REP(i, H) if (r_ile_kol[i] == 1) { FOR(c, 'A', 'Z') if (r_ile[i][c] > 0) { res.emplace_back('R', i+1, c); r_ile_kol[i]=0; REP(j, W) { int d = S[i][j]; c_ile[j][d]--; if (c_ile[j][d] == 0) c_ile_kol[j]--; } } bylo=true; } REP(i, W) if (c_ile_kol[i] == 1) { FOR(c, 'A', 'Z') if (c_ile[i][c] > 0) { res.emplace_back('K', i+1, c); c_ile_kol[i]=0; REP(j, H) { int d = S[j][i]; r_ile[j][d]--; if (r_ile[j][d]==0) r_ile_kol[j]--; } } bylo=true; } if (!bylo) break; } reverse(ALL(res)); cout << SIZE(res) << endl; REP(i, SIZE(res)) { cout << get<0>(res[i]) << " " << get<1>(res[i]) << " " << get<2>(res[i]) << endl; } } |