#include <iostream> #include <string> #include <sstream> #include <vector> #include <queue> using namespace std; struct Stats { static const int alphabet_size = 'Z'-'A'+1; int colors[alphabet_size]; int colors_left; Stats() { fill(colors, colors+alphabet_size, 0); colors_left = 0; } void add(char c) { if (colors[c-'A']++ == 0) colors_left++; } bool remove(char c) { if (--colors[c-'A'] == 0) if (--colors_left == 1) return true; return false; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n,m; cin >> n >> m; vector<string>V(n); for (auto& row : V) cin >> row; vector<Stats> RowStats(n), ColStats(m); queue<int> QR, QC; for (int r=0; r<n; r++) { for (int c=0; c<m; c++) RowStats[r].add(V[r][c]); if (RowStats[r].colors_left == 1) QR.push(r); } for (int c=0; c<m; c++) { for (int r=0; r<n; r++) ColStats[c].add(V[r][c]); if (ColStats[c].colors_left == 1) QC.push(c); } vector<string> Result; while (!QR.empty() || !QC.empty()) { if (!QR.empty()) { int r = QR.front(); QR.pop(); char color = '.'; for (int c=0; c<m; c++) if (V[r][c] != '.') { color = V[r][c]; V[r][c] = '.'; if (ColStats[c].remove(color)) QC.push(c); } if (color != '.') Result.push_back((ostringstream() << "R " << r+1 << " " << color).str()); } else { int c = QC.front(); QC.pop(); char color = '.'; for (int r=0; r<n; r++) if (V[r][c] != '.') { color = V[r][c]; V[r][c] = '.'; if (RowStats[r].remove(color)) QR.push(r); } if (color != '.') Result.push_back((ostringstream() << "K " << c+1 << " " << color).str()); } } cout << Result.size() << '\n'; for (auto it=Result.rbegin(); it!=Result.rend(); it++) cout << *it << '\n'; 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 | #include <iostream> #include <string> #include <sstream> #include <vector> #include <queue> using namespace std; struct Stats { static const int alphabet_size = 'Z'-'A'+1; int colors[alphabet_size]; int colors_left; Stats() { fill(colors, colors+alphabet_size, 0); colors_left = 0; } void add(char c) { if (colors[c-'A']++ == 0) colors_left++; } bool remove(char c) { if (--colors[c-'A'] == 0) if (--colors_left == 1) return true; return false; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n,m; cin >> n >> m; vector<string>V(n); for (auto& row : V) cin >> row; vector<Stats> RowStats(n), ColStats(m); queue<int> QR, QC; for (int r=0; r<n; r++) { for (int c=0; c<m; c++) RowStats[r].add(V[r][c]); if (RowStats[r].colors_left == 1) QR.push(r); } for (int c=0; c<m; c++) { for (int r=0; r<n; r++) ColStats[c].add(V[r][c]); if (ColStats[c].colors_left == 1) QC.push(c); } vector<string> Result; while (!QR.empty() || !QC.empty()) { if (!QR.empty()) { int r = QR.front(); QR.pop(); char color = '.'; for (int c=0; c<m; c++) if (V[r][c] != '.') { color = V[r][c]; V[r][c] = '.'; if (ColStats[c].remove(color)) QC.push(c); } if (color != '.') Result.push_back((ostringstream() << "R " << r+1 << " " << color).str()); } else { int c = QC.front(); QC.pop(); char color = '.'; for (int r=0; r<n; r++) if (V[r][c] != '.') { color = V[r][c]; V[r][c] = '.'; if (RowStats[r].remove(color)) QR.push(r); } if (color != '.') Result.push_back((ostringstream() << "K " << c+1 << " " << color).str()); } } cout << Result.size() << '\n'; for (auto it=Result.rbegin(); it!=Result.rend(); it++) cout << *it << '\n'; return 0; } |