#include <iostream> #include <vector> #include <algorithm> #include <queue> #include <string> #include <unordered_map> using namespace std; int main() { std::ios_base::sync_with_stdio(false); int h, w; cin >> h >> w; vector<string> image; for (int i = 0; i < h; i++) { string s; cin >> s; image.push_back(s); } vector< unordered_map<char, int> > row_colors(h, unordered_map<char,int>()), column_colors(w, unordered_map<char,int>()); vector<bool> column_covered(w, false), row_covered(h, false); queue<pair<int,char>> row_q, column_q; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { row_colors[i][image[i][j]]++; if (row_colors[i][image[i][j]] == w) { row_q.push({i, image[i][j]}); } column_colors[j][image[i][j]]++; if (column_colors[j][image[i][j]] == h) { column_q.push({j, image[i][j]}); } } } vector<string> instructions; while (!row_q.empty() || !column_q.empty()) { if (!row_q.empty()) { auto r = row_q.front(); row_q.pop(); if (row_colors[r.first].empty()) { continue; } instructions.push_back("R " + to_string(r.first + 1) + " " + r.second); for (int i = 0; i < w; i++) { if (!column_covered[i]) { --column_colors[i][image[r.first][i]]; if (column_colors[i][image[r.first][i]] == 0) { column_colors[i].erase(column_colors[i].find(image[r.first][i])); if (column_colors[i].size() == 1) { // cout << "pusz " << i << " " << column_colors[i].begin()->first << endl; column_q.push({i, column_colors[i].begin()->first}); } } } } row_covered[r.first] = true; } else { auto c = column_q.front(); column_q.pop(); if (column_colors[c.first].empty()) { continue; } instructions.push_back("K " + to_string(c.first + 1) + " " + c.second); for (int i = 0; i < h; i++) { if (!row_covered[i]) { --row_colors[i][image[i][c.first]]; if (row_colors[i][image[i][c.first]] == 0) { row_colors[i].erase(row_colors[i].find(image[i][c.first])); if (row_colors[i].size() == 1) { // cout << "pusz " << i << " " << row_colors[i].begin()->first << endl; row_q.push({i, row_colors[i].begin()->first}); } } } } column_covered[c.first] = true; } } cout << instructions.size() << '\n'; reverse(instructions.begin(), instructions.end()); for (auto inst: instructions) { cout << inst << '\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 | #include <iostream> #include <vector> #include <algorithm> #include <queue> #include <string> #include <unordered_map> using namespace std; int main() { std::ios_base::sync_with_stdio(false); int h, w; cin >> h >> w; vector<string> image; for (int i = 0; i < h; i++) { string s; cin >> s; image.push_back(s); } vector< unordered_map<char, int> > row_colors(h, unordered_map<char,int>()), column_colors(w, unordered_map<char,int>()); vector<bool> column_covered(w, false), row_covered(h, false); queue<pair<int,char>> row_q, column_q; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { row_colors[i][image[i][j]]++; if (row_colors[i][image[i][j]] == w) { row_q.push({i, image[i][j]}); } column_colors[j][image[i][j]]++; if (column_colors[j][image[i][j]] == h) { column_q.push({j, image[i][j]}); } } } vector<string> instructions; while (!row_q.empty() || !column_q.empty()) { if (!row_q.empty()) { auto r = row_q.front(); row_q.pop(); if (row_colors[r.first].empty()) { continue; } instructions.push_back("R " + to_string(r.first + 1) + " " + r.second); for (int i = 0; i < w; i++) { if (!column_covered[i]) { --column_colors[i][image[r.first][i]]; if (column_colors[i][image[r.first][i]] == 0) { column_colors[i].erase(column_colors[i].find(image[r.first][i])); if (column_colors[i].size() == 1) { // cout << "pusz " << i << " " << column_colors[i].begin()->first << endl; column_q.push({i, column_colors[i].begin()->first}); } } } } row_covered[r.first] = true; } else { auto c = column_q.front(); column_q.pop(); if (column_colors[c.first].empty()) { continue; } instructions.push_back("K " + to_string(c.first + 1) + " " + c.second); for (int i = 0; i < h; i++) { if (!row_covered[i]) { --row_colors[i][image[i][c.first]]; if (row_colors[i][image[i][c.first]] == 0) { row_colors[i].erase(row_colors[i].find(image[i][c.first])); if (row_colors[i].size() == 1) { // cout << "pusz " << i << " " << row_colors[i].begin()->first << endl; row_q.push({i, row_colors[i].begin()->first}); } } } } column_covered[c.first] = true; } } cout << instructions.size() << '\n'; reverse(instructions.begin(), instructions.end()); for (auto inst: instructions) { cout << inst << '\n'; } return 0; } |