#include <iostream> #include <vector> #include <queue> #define nl '\n' using namespace std; struct paint{ char type; int pos; int color; }; int rows[2001][26], cols[2001][26]; vector<paint> moves; queue<paint> q; int n, m; int good(int arr[]) { int existent = -1; for(int c = 0; c <= 25; c++){ //cerr<<arr[c]<<' '; if(arr[c]){ if(existent != -1){ existent = -1; break; }; existent = c; } } //cerr<<nl; return existent; } int main() { cin.tie(0)->sync_with_stdio(0); cin>>n>>m; for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ char c; cin>>c; rows[i][c-'A']++; cols[j][c-'A']++; } } for(int i=1; i<=n; i++){ int color = good(rows[i]); if(color != -1){ paint h = {'R', i, color}; q.push(h); } } for(int i=1; i<=m; i++){ int color = good(cols[i]); if(color != -1){ paint h = {'K', i, color}; q.push(h); } } int rozp_count = 0; while(q.size()){ rozp_count++; auto [t, ind, col] = q.front(); //cerr<<t<<' '<<ind<<' '<<col<<nl; q.pop(); if(t=='R'){ if(good(rows[ind]) == -1) continue; rows[ind][col] = 0; for(int i=1; i<=m; i++){ rozp_count++; if(cols[i][col]) cols[i][col]--; int color = good(cols[i]); //cerr<<i<<' '<<color<<nl; if(color != -1){ paint h = {'K', i, color}; q.push(h); } } } if(t=='K'){ if(good(cols[ind]) == -1) continue; cols[ind][col] = 0; for(int i=1; i<=n; i++){ if(rows[i][col]) rows[i][col]--; int color = good(rows[i]); //cerr<<i<<' '<<color<<nl; if(color != -1){ paint h = {'R', i, color}; q.push(h); } } } moves.push_back({t, ind, col}); } cout<<moves.size()<<nl; while(moves.size()){ auto [t, ind, col] = moves.back(); moves.pop_back(); cout<<t<<' '<<ind<<' '<<(char)(col+'A')<<nl; } //cerr<<rozp_count<<nl; 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 | #include <iostream> #include <vector> #include <queue> #define nl '\n' using namespace std; struct paint{ char type; int pos; int color; }; int rows[2001][26], cols[2001][26]; vector<paint> moves; queue<paint> q; int n, m; int good(int arr[]) { int existent = -1; for(int c = 0; c <= 25; c++){ //cerr<<arr[c]<<' '; if(arr[c]){ if(existent != -1){ existent = -1; break; }; existent = c; } } //cerr<<nl; return existent; } int main() { cin.tie(0)->sync_with_stdio(0); cin>>n>>m; for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ char c; cin>>c; rows[i][c-'A']++; cols[j][c-'A']++; } } for(int i=1; i<=n; i++){ int color = good(rows[i]); if(color != -1){ paint h = {'R', i, color}; q.push(h); } } for(int i=1; i<=m; i++){ int color = good(cols[i]); if(color != -1){ paint h = {'K', i, color}; q.push(h); } } int rozp_count = 0; while(q.size()){ rozp_count++; auto [t, ind, col] = q.front(); //cerr<<t<<' '<<ind<<' '<<col<<nl; q.pop(); if(t=='R'){ if(good(rows[ind]) == -1) continue; rows[ind][col] = 0; for(int i=1; i<=m; i++){ rozp_count++; if(cols[i][col]) cols[i][col]--; int color = good(cols[i]); //cerr<<i<<' '<<color<<nl; if(color != -1){ paint h = {'K', i, color}; q.push(h); } } } if(t=='K'){ if(good(cols[ind]) == -1) continue; cols[ind][col] = 0; for(int i=1; i<=n; i++){ if(rows[i][col]) rows[i][col]--; int color = good(rows[i]); //cerr<<i<<' '<<color<<nl; if(color != -1){ paint h = {'R', i, color}; q.push(h); } } } moves.push_back({t, ind, col}); } cout<<moves.size()<<nl; while(moves.size()){ auto [t, ind, col] = moves.back(); moves.pop_back(); cout<<t<<' '<<ind<<' '<<(char)(col+'A')<<nl; } //cerr<<rozp_count<<nl; return 0; } |