/* P-I-2 Zasypane mesto * Jakub Ruzicka * ctete mesto.txt */#include <iostream>#include <fstream>#include <vector>using namespace std;int main ( int argc, char *argv[] ){// vstupni a vystupni soubory...ifstream vstup("mesto.in");ofstream vystup("mesto.out");// nacteme zakladni promenneunsigned int m,n;unsigned long int k;if( !( (vstup >> m) && (vstup >> n) && (vstup >> k) ) ) { cerr << "Chyba na vstupu(nepodarilo se nacist zakladni promenne)\n"; exit(EXIT_FAILURE);}unsigned int mesto[m][n]; // pole, do ktereho si ulozime mestounsigned int r=0,s=0; // na kterem radku a sloupci zrovna jsme ?unsigned int p,vypln=1; // p - kolik nasledujicich poli je tvoreno piskem/kamenim; vypln - pisek/kameni ?// pro jistotu vynulujeme mesto, 0 pro kameni, 1 pro pisekfor(unsigned int e=0;e<n;e++) for(unsigned int f=0;f<m;f++) mesto[f][e]=0;// nacteme mesto do pole...for(unsigned long int i=0;i < (k-1)*2;i++) { vstup >> p; for(unsigned int j=0;j<p;j++) { // vyplnme naledujicich p poli mesto[r][s]=vypln; r++; if(r>=m) { // jsme na konci radku r=0; s++; // dalsi radek if(s>=n) { // presahli jsme plochu mesta - konec cerr << "Chyba na vstupu (pocet zadanych poli je vetsi nez plocha mesta)\n"; //exit(EXIT_FAILURE); } } } if(vypln) vypln=0; else vypln=1; // prohodime vypln}// tak a ted to dulezite, spocitame mistnosti.// postupne projdeme cele mesto. kdyz narazime na pisek, zaznamename si// nalezenou mistnost a celou ji zaplnime, aby pozdeji nebyla pripocitana// znovu pri nalezu jeji dalsi casti.vector<unsigned int> x,y; // souradnice policek pisku v mistnostivector<unsigned int>::iterator ii;unsigned int X,Y; // pomocne promenne, ktere snad usetri trochu vypocet. casuunsigned long int pocet=0; // pocet mest// tak, jdeme na to...for(unsigned int f=0;f<n;f++) for(unsigned int e=0;e<m;e++) if(mesto[e][f]) { //nasli jsme mistnost pocet++; x.clear(); y.clear(); x.push_back(e); y.push_back(f); while(!x.empty()) { // dokud jsou nejaka policka s piskem, hledejme jejich sousedy X=x[0];Y=y[0]; // nebudeme prece zbytecne porad hldeat ve vektoru, cas jsou penize // relativne prasacke opakovani, jde nam vsak o rychlost. if((Y>0) && (mesto[X][Y-1])) { x.push_back(X); y.push_back(Y-1); } if((Y<n-1) && (mesto[X][Y+1])) { x.push_back(X); y.push_back(Y+1); } if((X>0) && (mesto[X-1][Y])) { x.push_back(X-1); y.push_back(Y); } if((X<m-1) && (mesto[X+1][Y])) { x.push_back(X+1); y.push_back(Y); } mesto[X][Y]=0; // nasli jsme co jsme pripadne sousedy, "zasypeme" policko. ii = x.begin(); x.erase( ii ); ii = y.begin(); y.erase( ii ); } }vystup << pocet;vystup.close(); vstup.close();return EXIT_SUCCESS;}