#include <cstdio> #include <list> #include <stack> #define DEBUG false using namespace std; char tab[2005][2005]; int n,m; struct Ruch{ char poz; int nr; char kolor; }r; list<int>wiersz,kolumna; list<int>::iterator itX,itY,it; stack<Ruch>ruch; int main(){ scanf(" %d %d",&n,&m); for(int i=0; i<n; i++){ scanf(" %s",&tab[i]); } for(int i=0; i<n; i++) wiersz.push_back(i); for(int i=0; i<m; i++) kolumna.push_back(i); bool pion = true; int suma = n*m; int restY = n, restX = m; while(suma>0){ if(pion){ for(itX = kolumna.begin(); itX!=kolumna.end(); ){ itY = wiersz.begin(); char kolor = tab[*itY][*itX]; int ile = 0; for( itY = wiersz.begin(); itY!=wiersz.end(); itY++){ if(kolor == tab[*itY][*itX]) ile++; else break; } if( ile == restY ){ //zapisz ruch na stosie r.poz='K'; r.nr = *itX; r.kolor = kolor; ruch.push(r); //usun kolumne z listy it = itX; itX++; kolumna.remove(*it); if(DEBUG)printf("Usunieto kolumne %d, odjeto:%d\n",*it,ile); suma -= ile; restX--; } else itX++; } if(DEBUG)printf("Zostalo %d pol\n",suma); pion = false; } else { for(itY = wiersz.begin(); itY!=wiersz.end(); ){ itX = kolumna.begin(); char kolor = tab[*itY][*itX]; int ile = 0; for( itX = kolumna.begin(); itX!=kolumna.end(); itX++){ if(kolor == tab[*itY][*itX]) ile++; else break; } if( ile == restX ){ //zapisz ruch na stosie r.poz='R'; r.nr = *itY; r.kolor = kolor; ruch.push(r); //usun kolumne z listy it = itY; itY++; wiersz.remove(*it); if(DEBUG)printf("Usunieto wiersz %d, odjeto:%d\n",*it,ile); suma -= ile; restY--; } else itY++; } if(DEBUG)printf("Zostalo %d pol\n",suma); pion = true; } } printf("%d\n",ruch.size()); while(!ruch.empty()){ r=ruch.top(); ruch.pop(); printf("%c %d %c\n",r.poz,r.nr+1,r.kolor); } 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 | #include <cstdio> #include <list> #include <stack> #define DEBUG false using namespace std; char tab[2005][2005]; int n,m; struct Ruch{ char poz; int nr; char kolor; }r; list<int>wiersz,kolumna; list<int>::iterator itX,itY,it; stack<Ruch>ruch; int main(){ scanf(" %d %d",&n,&m); for(int i=0; i<n; i++){ scanf(" %s",&tab[i]); } for(int i=0; i<n; i++) wiersz.push_back(i); for(int i=0; i<m; i++) kolumna.push_back(i); bool pion = true; int suma = n*m; int restY = n, restX = m; while(suma>0){ if(pion){ for(itX = kolumna.begin(); itX!=kolumna.end(); ){ itY = wiersz.begin(); char kolor = tab[*itY][*itX]; int ile = 0; for( itY = wiersz.begin(); itY!=wiersz.end(); itY++){ if(kolor == tab[*itY][*itX]) ile++; else break; } if( ile == restY ){ //zapisz ruch na stosie r.poz='K'; r.nr = *itX; r.kolor = kolor; ruch.push(r); //usun kolumne z listy it = itX; itX++; kolumna.remove(*it); if(DEBUG)printf("Usunieto kolumne %d, odjeto:%d\n",*it,ile); suma -= ile; restX--; } else itX++; } if(DEBUG)printf("Zostalo %d pol\n",suma); pion = false; } else { for(itY = wiersz.begin(); itY!=wiersz.end(); ){ itX = kolumna.begin(); char kolor = tab[*itY][*itX]; int ile = 0; for( itX = kolumna.begin(); itX!=kolumna.end(); itX++){ if(kolor == tab[*itY][*itX]) ile++; else break; } if( ile == restX ){ //zapisz ruch na stosie r.poz='R'; r.nr = *itY; r.kolor = kolor; ruch.push(r); //usun kolumne z listy it = itY; itY++; wiersz.remove(*it); if(DEBUG)printf("Usunieto wiersz %d, odjeto:%d\n",*it,ile); suma -= ile; restY--; } else itY++; } if(DEBUG)printf("Zostalo %d pol\n",suma); pion = true; } } printf("%d\n",ruch.size()); while(!ruch.empty()){ r=ruch.top(); ruch.pop(); printf("%c %d %c\n",r.poz,r.nr+1,r.kolor); } return 0; } |