Analysis: Cow Art by Brian Dean
This problem involves running a "flood fill" algorithm to visit each region, marking it as visited, until all regions are visited and counted. In my code below, I use a recursive "depth-first" search to fill in each successive region. The visit() function marks a cell as being visited and then recursively visits all neighboring cells that are part of the same region.
#include <iostream> #include <fstream> #include <string> #define MAX_N 100 using namespace std; string A[MAX_N]; int N; bool valid[256][256]; bool visited[MAX_N][MAX_N]; void visit(int i, int j) { if (visited[i][j]) return; visited[i][j] = true; if (i > 0 && valid[A[i-1][j]][A[i][j]]) visit(i-1, j); if (j > 0 && valid[A[i][j-1]][A[i][j]]) visit(i, j-1); if (i < N-1 && valid[A[i+1][j]][A[i][j]]) visit(i+1, j); if (j < N-1 && valid[A[i][j+1]][A[i][j]]) visit(i, j+1); } int solve(void) { int count = 0; for (int i=0; i<N; i++) for (int j=0; j<N; j++) visited[i][j] = false; for (int i=0; i<N; i++) for (int j=0; j<N; j++) if (!visited[i][j]) { count++; visit(i,j); } return count; } int main(void) { ifstream fin("cowart.in"); fin >> N; for (int i=0; i<N; i++) fin >> A[i]; fin.close(); valid['R']['R'] = valid['G']['G'] = valid['B']['B'] = true; int regions_human = solve(); valid['R']['G'] = valid['G']['R'] = true; int regions_cow = solve(); ofstream fout("cowart.out"); fout << regions_human << " " << regions_cow << "\n"; fout.close(); return 0; }