The Castle
        IOI'94
       
        题目大意：
                http://www.nocow.cn/index.php/Translate:USACO/castle
               
        分析:
            题面和要求有点啰嗦，不过总的来说还是好理解的。给定一个城堡的规格，让你求
        在围墙内可以互相联通的小房间组成的大房间的个数和尺寸。另外设法推倒一面墙，让
        两个大房间合并成更大的房间。
            这题嘛，我也不知道该分析什么，当时一看到就用图论观点做了。下面给出几个入
        手点(其实和NOCOW的大同小异了):
       
        1.并查集
            显然一堆互相联通的小房间属于同一个等价集 ，对二位的数据扫一遍然后映射到一
        维的并查集上求并。最后森林的个数自然就是大房间的个数了，一颗树的重量就是房间的
        尺寸了。这个出来推墙就好办，枚举每一面合法的墙，两边的房间求一次树根，如果不同
        根（重要细节，如果墙两次的房间是同一个大房间的话就错了~）则按要求做比较。最后
        打印，收工。
       
         2.floodfill
            刚开始我也不清楚这个做法（之前确实不知道，汗~）。后来看了下usaco的论文。
        其实还是很形象的，就是用BFS往上灌水，任何联通的区域都会被当前这次灌的水淹到。
        不同次灌水淹到的区域自然就是不同的大房间了。仍然不清楚的请看usaco上的论文。
       
         3.硬搞
            实在不会的何必想那么多呢，让小房间构成n*m的无向图，没有门的房间自然
        相邻。直接DFS联通分支。打印，收工。
       
        下面给出我的并查代码的 main(),求出门的方位使用位运算

int main(){
        for(step=0;step<2600;step++) ufs[step]=-1;
        fscanf(fin,"%d%d",&n,&m);
        for(step=0;step<m;step++)
                for(step2=0;step2<n;step2++)
                        fscanf(fin,"%d",&room[step][step2]);
               
        for(step=0;step<m;step++)
                for(step2=0;step2<n;step2++){
                        tmpNum=room[step][step2];
                        digit=0;
                        pos1=step*n+step2;
                        while(1){
                                if( (tmpNum&1) ==0){
                                        pos2=(step+door[digit][0])*n+(step2+door[digit][1]);
                                        ufsF(ufs,pos1,pos2);   // 并查相邻两个房间
                                }
                                tmpNum>>=1;
                                digit++;
                                if(tmpNum==0&&digit>3) break;
                        }
                }
        roomNum=0;
        maxSize=0;
        for(step=0;step<m*n;step++){
                if(ufs[step]<0){
                        if(ufs[step]*-1>maxSize) maxSize=ufs[step]*-1;
                        roomNum++;
                }
        }
        fprintf(fout,"%d\n%d\n",roomNum,maxSize);
       
        maxAdd=0;
        for(step2=0;step2<n;step2++)
            for(step=m-1;step>-1;step--){   
                tmpNum=room[step][step2];
                digit=0;
                pos1=(step)*n+step2;
                while(1){
                     if((tmpNum&1)==1){
                        if(digit==2||digit==1){
                           // 从左下到右上检查每个小房间与右、上有墙隔着的小房间，若不同根则计算

                           if(step+door[digit][0]>-1&&step2+door[digit][1]<n){  // 门不是墙壁
                               pos2=(step+door[digit][0])*n+(step2+door[digit][1]);
                               root1=Find(ufs,pos1);
                               root2=Find(ufs,pos2);
                               if(root1!=root2){
                                  if(maxAdd< (ufs[root1]+ufs[root2])*-1 ){
                                     maxAdd=(ufs[root1]+ufs[root2])*-1;
                                     rm=step+1; rn=step2+1;
                                     rd=(digit==1)?'N':'E';
                                  }
                               }
                           }
                       }
                     }
                     tmpNum>>=1;
                     digit++;
                     if(tmpNum==0&&digit>3) break;
                }       
           }
        fprintf(fout,"%d\n%d %d %c\n",maxAdd,rm,rn,rd);
        return 0;
}