zoj 1805 Squadtrees

#include<iostream>#include<math.h>#include<cstring>#include<map>using namespace std;const int maxsize=128;char MAP[maxsize][maxsize];int acount,bcount;struct quadtree{quadtree *father;quadtree *q[4];string value;int level;bool fstate;int state;bool operator == (quadtree temp){return temp.value==value;}quadtree(){for(int i=0;i<4;i++)q[i]=NULL;father=NULL;level=0;fstate=true;}};quadtree *DFS(int r,int c,int s){int i;bool f=true;quadtree *temp=new quadtree;if(s==1){temp->value='0';temp->value+=MAP[r][c];return temp;}s/=2;temp->q[0]=DFS(r,c,s);temp->q[1]=DFS(r,c+s,s);temp->q[2]=DFS(r+s,c,s);temp->q[3]=DFS(r+s,c+s,s);for(int i=0;i<4;i++){temp->q[i]->father=temp;temp->q[i]->state=i;}for(i=1;i<4;++i){if(!(*temp->q[0]==*temp->q[i])||temp->q[0]->value=="1"){f=false;break;}}if(f){temp->value=temp->q[0]->value;for(i=0;i<4;++i){delete temp->q[i];temp->q[i]=NULL;}}elsetemp->value="1";return temp;}multimap<int,quadtree*> maps;void DFS(quadtree *node){if(node){acount++;if(node->value=="1"){bool flag=true;for(int i=0;i<4;i++){if(node->q[i])if(node->q[i]->value=="1")flag=false;}if(flag){node->level=1;maps.insert(make_pair(1,node));}}for(int i=0;i<4;i++)DFS(node->q[i]);}}bool com(quadtree *node1,quadtree *node2){if(node1->value==node2->value){if(node1->q[0]){for(int i=0;i<4;i++){if(!com(node1->q[i],node2->q[i]))return false;}}elsereturn true;}elsereturn false;}void setnum(quadtree *node){while(node->father){if(node->father->level<node->level+1)node->father->level=node->level+1;node=node->father;}}void inmap(quadtree *node){if(node){if(node->level!=1&&node->level)maps.insert(make_pair(node->level,node));for(int i=0;i<4;i++)inmap(node->q[i]);}}void deltree(quadtree *&node){if(node){for(int i=0;i<4;i++)deltree(node->q[i]);delete node;}}void able(quadtree *node){int maxl=node->level,j,i=0;multimap<int,quadtree*>::iterator it;for(j=1,it=maps.begin();j<maxl&&it!=maps.end();++it,j++){if(maps.count(j)==1)continue;else{quadtree **p;p=new quadtree*[maps.count(j)];for(i=0,it=maps.lower_bound(j);it!=maps.upper_bound(j);++it){p[i]=it->second;i++;}int z=maps.count(j);for(int i=0;i<z;i++)for(int k=i+1;k<z;k++)if(com(p[i],p[k]))p[k]->fstate=false;}}}void KDFS(quadtree *node){if(node){if(node->fstate){bcount++;for(int i=0;i<4;i++)KDFS(node->q[i]);}}}int main(){int n,m;while(cin>>n>>m&&n&&m){quadtree *order;acount=bcount=0;maps.clear();int max;if(m>n)max=m;elsemax=n;int N=0,i=0;while(N<max)N=pow(2.0,i++);memset(MAP,'0',sizeof(MAP));for(i=0;i<n;i++)for(int j=0;j<m;j++)cin>>MAP[i][j];order=DFS(0,0,N);DFS(order);multimap<int,quadtree*>::iterator it;for(it=maps.begin();it!=maps.end();++it){if(it->first==1)setnum(it->second);}inmap(order);able(order);KDFS(order);cout<<acount<<' '<<bcount<<endl;deltree(order);}return 0;}