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;
}