/* Wybierze on sobie docelową kolorową planszę o wymiarach n×m, a grę rozpocznie z planszą n×m, na której żadne pole nie ma koloru. W jednym ruchu może on wybrać rząd lub kolumnę i przemalować wszystkie pola w nim/niej wybranym przez siebie kolorem (zwróć uwagę na to, że daje mu to większą swobodę niż w grze przedstawionej na obrazkach powyżej, gdzie wiersze i kolumny miały narzucone kolory). Aby nieco sformalizować zadanie, wszystkie kolory oznaczył wielkimi literami alfabetu angielskiego. Czy pomożesz mu i napiszesz program, który dla każdej zadanej przez niego planszy poda ciąg ruchów, który poprawnie stworzy docelowy układ kolorów? Możesz założyć, że dostaniesz dane wejściowe, w których ten cel można osiągnąć w co najwyżej n + m ruchach */ #include <bits/stdc++.h> using namespace std; int n, m; char a[2001][2001]; queue<pair<bool, int>> ready; int cntH[2001][200], cntV[2001][200]; bool usedH[2001], usedV[2001]; int checkV(int x){ //cout << "checkV " << x << "\n"; int cnt = 0; int clr = 0; for(int i = 'A'; i <= 'Z'; i++){ if(cntV[x][i] > 0){ cnt++; clr = i; } } if(cnt == 1){ return clr; } return 0; } int checkH(int x){ //cout << "checkH " << x << "\n"; int cnt = 0; int clr = 0; for(int i = 'A'; i <= 'Z'; i++){ if(cntH[x][i] > 0){ cnt++; clr = i; } } if(cnt == 1){ return clr; } return 0; } stack<pair<bool, pair<int, char>>> res; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cin >> a[i][j]; cntH[i][a[i][j]]++; cntV[j][a[i][j]]++; } } for(int i = 0; i < n; i++){ int clr = checkH(i); if(clr != 0){ //cout << "row " << i + 1 << " " << (char)clr << " is ready\n"; ready.push({0, i}); usedH[i] = 1; } } for(int i = 0; i < m; i++){ int clr = checkV(i); if(clr != 0){ //cout << "col " << i + 1 << " " << (char)clr << " is ready\n"; ready.push({1, i}); usedV[i] = 1; } } while(!ready.empty()){ pair<bool, int> p = ready.front(); ready.pop(); if(p.first == 0){ int clr = checkH(p.second); if(clr != 0){ res.push({0, {p.second, clr}}); for(int i = 0; i < m; i++){ if(usedV[i]){ continue; } cntV[i][a[p.second][i]]--; if(cntV[i][a[p.second][i]] == 0){ int clr2 = checkV(i); if(clr2 != 0){ ready.push({1, i}); usedV[i] = 1; } } } } } else{ int clr = checkV(p.second); if(clr != 0){ res.push({1, {p.second, clr}}); for(int i = 0; i < n; i++){ if(usedH[i]){ continue; } cntH[i][a[i][p.second]]--; if(cntH[i][a[i][p.second]] == 0){ int clr2 = checkH(i); if(clr2 != 0){ ready.push({0, i}); usedH[i] = 1; } } } } } } cout << res.size() << "\n"; while(!res.empty()){ pair<bool, pair<int, char>> p = res.top(); res.pop(); if(p.first == 0){ cout << "R " << p.second.first + 1 << " " << p.second.second << "\n"; } else{ cout << "K " << p.second.first + 1 << " " << p.second.second << "\n"; } } }
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 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 | /* Wybierze on sobie docelową kolorową planszę o wymiarach n×m, a grę rozpocznie z planszą n×m, na której żadne pole nie ma koloru. W jednym ruchu może on wybrać rząd lub kolumnę i przemalować wszystkie pola w nim/niej wybranym przez siebie kolorem (zwróć uwagę na to, że daje mu to większą swobodę niż w grze przedstawionej na obrazkach powyżej, gdzie wiersze i kolumny miały narzucone kolory). Aby nieco sformalizować zadanie, wszystkie kolory oznaczył wielkimi literami alfabetu angielskiego. Czy pomożesz mu i napiszesz program, który dla każdej zadanej przez niego planszy poda ciąg ruchów, który poprawnie stworzy docelowy układ kolorów? Możesz założyć, że dostaniesz dane wejściowe, w których ten cel można osiągnąć w co najwyżej n + m ruchach */ #include <bits/stdc++.h> using namespace std; int n, m; char a[2001][2001]; queue<pair<bool, int>> ready; int cntH[2001][200], cntV[2001][200]; bool usedH[2001], usedV[2001]; int checkV(int x){ //cout << "checkV " << x << "\n"; int cnt = 0; int clr = 0; for(int i = 'A'; i <= 'Z'; i++){ if(cntV[x][i] > 0){ cnt++; clr = i; } } if(cnt == 1){ return clr; } return 0; } int checkH(int x){ //cout << "checkH " << x << "\n"; int cnt = 0; int clr = 0; for(int i = 'A'; i <= 'Z'; i++){ if(cntH[x][i] > 0){ cnt++; clr = i; } } if(cnt == 1){ return clr; } return 0; } stack<pair<bool, pair<int, char>>> res; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cin >> a[i][j]; cntH[i][a[i][j]]++; cntV[j][a[i][j]]++; } } for(int i = 0; i < n; i++){ int clr = checkH(i); if(clr != 0){ //cout << "row " << i + 1 << " " << (char)clr << " is ready\n"; ready.push({0, i}); usedH[i] = 1; } } for(int i = 0; i < m; i++){ int clr = checkV(i); if(clr != 0){ //cout << "col " << i + 1 << " " << (char)clr << " is ready\n"; ready.push({1, i}); usedV[i] = 1; } } while(!ready.empty()){ pair<bool, int> p = ready.front(); ready.pop(); if(p.first == 0){ int clr = checkH(p.second); if(clr != 0){ res.push({0, {p.second, clr}}); for(int i = 0; i < m; i++){ if(usedV[i]){ continue; } cntV[i][a[p.second][i]]--; if(cntV[i][a[p.second][i]] == 0){ int clr2 = checkV(i); if(clr2 != 0){ ready.push({1, i}); usedV[i] = 1; } } } } } else{ int clr = checkV(p.second); if(clr != 0){ res.push({1, {p.second, clr}}); for(int i = 0; i < n; i++){ if(usedH[i]){ continue; } cntH[i][a[i][p.second]]--; if(cntH[i][a[i][p.second]] == 0){ int clr2 = checkH(i); if(clr2 != 0){ ready.push({0, i}); usedH[i] = 1; } } } } } } cout << res.size() << "\n"; while(!res.empty()){ pair<bool, pair<int, char>> p = res.top(); res.pop(); if(p.first == 0){ cout << "R " << p.second.first + 1 << " " << p.second.second << "\n"; } else{ cout << "K " << p.second.first + 1 << " " << p.second.second << "\n"; } } } |