/* FILE: stomp.cpp last change: 30-Jul-2013 author: Romeo Rizzi * an O(mn) time and memory solver identifying the parity of the number of 1's in each connected component. */ #define NDEBUG // NDEBUG definita nella versione che consegno #include #ifndef NDEBUG # include // uso di cin e cout non consentito in versione finale #endif #include #include using namespace std; const int MAX_M = 10000; const int MAX_N = 10000; int m, n; int field[MAX_M+2][MAX_N+2]; int DFS(int i, int j) { if( field[i][j] == 2) return 0; int risp = field[i][j]; field[i][j] = 2; return risp + DFS(i, j+1) + DFS(i, j-1) + DFS(i+1, j) + DFS(i-1, j); } int main() { ifstream fin("input.txt"); assert( fin ); fin >> m >> n; // immersion of the field in a framework of sentinels: for(int i = 0; i <= m+1; i++) field[i][0] = field[i][n+1] = 2; for(int j = 0; j <= n+1; j++) field[0][j] = field[m+1][j] = 2; // reading the field from file: //for(int i = 1; i <= m; i++) // for(int j = 1; j <= n; j++) // fin >> field[i][j]; // // BUT LET'S DO IT FASTER: string line; getline(fin, line); for(int i = 1; i <= m; i++) { getline(fin, line); const char *p = line.c_str(); for(int j = 1; j <= n; j++) { while( *p < '0' || *p > '2' ) p++; field[i][j] = *p - '0'; p++; } } // END fast reading. (Ho ottimizzato questa parte con questo accrocchio solo perche' mi sono reso conto che la lettura da input era il collo di bottiglia. Non e' pero' il tipo di ottimizzazioni che richiedo, e pertanto nella valutazione dei vostri codici ho abbonato i tempi per la lettura da input). fin.close(); int num_odd_components = 0; for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++) if( field[i][j] != 2) num_odd_components += DFS(i,j) % 2; ofstream fout("output.txt"); assert( fout ); fout << num_odd_components << endl; fout.close(); return 0; }