// squadT.cc // squad tree problem // T Feil #include using namespace std; int A[128][128]; struct node { int color; node * link1; node * link2; node * link3; node * link4; }; node * root; node *getNewNode(){ node *r = new node; r->color = -1; r->link1 = NULL; r->link2 = NULL; r->link3 = NULL; r->link4 = NULL; return r; } void zeroMatrix(){ for(int i=0;i<128;i++) for(int j=0;j<128;j++) A[i][j]=0; } void getMatrix(int &r, int &c){ char x; zeroMatrix(); for(int i=0;i>x; A[i][j] = x-'0'; } if(r>64) r=128; else if(r>32) r=64; else if(r>16) r=32; else if(r>8) r=16; else if(r>4) r=8; else if(r>2) r=4; if(c>64) c=128; else if(c>32) c=64; else if(c>16) c=32; else if(c>8) c=16; else if(c>4) c=8; else if(c>2) c=4; if(c>r) r=c; else c=r; } void printMatrix(int r, int c){ for(int i=0;icolor = A[X][Y]; else if (allBlack(X,Y,dim)) root->color = 1; else if (allWhite(X,Y,dim)) root->color = 0; else { root->link1 = getNewNode(); root->link2 = getNewNode(); root->link3 = getNewNode(); root->link4 = getNewNode(); int half = dim/2; buildQuad(X,Y,half,root->link1); buildQuad(X,Y+half,half,root->link2); buildQuad(X+half,Y,half,root->link3); buildQuad(X+half,Y+half,half,root->link4); } } void printTree(node * r){ if(r==NULL) return; if(r->color==-2) return; if(r->color != -1) cout<color<<' '; else{ printTree(r->link1); printTree(r->link2); printTree(r->link3); printTree(r->link4); cout<color==-2) return 0; if (r->color!=-1) return 1; else return(countNodes(r->link1) + countNodes(r->link2) + countNodes(r->link3) + countNodes(r->link4) + 1); } bool sameTree(node *x, node *y){ if((x==NULL) || (y==NULL) ) return false; if((x->color>-1) && (x->color == y->color)) return true; // if(y->color!=-2) return(sameTree(x->link1,y->link1) && sameTree(x->link2,y->link2) && sameTree(x->link3,y->link3) && sameTree(x->link4,y->link4)); // else // return false; } void FindAllMatches(node * x,node *y){ if(y->color!=-1) return; if(y==x) return; if(sameTree(x,y)){ // printTree(y); y->color=-2; } else{ FindAllMatches(x,y->link1); FindAllMatches(x,y->link2); FindAllMatches(x,y->link3); FindAllMatches(x,y->link4); } } void makeSquad(node* x){ if(x->color!= -1) return; FindAllMatches(x,root); makeSquad(x->link1); makeSquad(x->link2); makeSquad(x->link3); makeSquad(x->link4); } int main(){ int r,c; cin>>r>>c; while(r>0){ getMatrix(r,c); // printMatrix(r,c); root = getNewNode(); buildQuad(0,0,r,root); //printTree(root); int count = countNodes(root); cout<color==-1){ makeSquad(root->link1); makeSquad(root->link2); makeSquad(root->link3); makeSquad(root->link4); } //printTree(root); count = countNodes(root); cout<>r>>c; } return 0; }