The Castle
        IOI'94
       
        題目大意：
                http://www.nocow.cn/index.php/Translate:USACO/castle
               
        分析:
            題面和要求有點(diǎn)啰嗦，不過(guò)總的來(lái)說(shuō)還是好理解的。給定一個(gè)城堡的規(guī)格，讓你求
        在圍墻內(nèi)可以互相聯(lián)通的小房間組成的大房間的個(gè)數(shù)和尺寸。另外設(shè)法推倒一面墻，讓
        兩個(gè)大房間合并成更大的房間。
            這題嘛，我也不知道該分析什么，當(dāng)時(shí)一看到就用圖論觀點(diǎn)做了。下面給出幾個(gè)入
        手點(diǎn)(其實(shí)和NOCOW的大同小異了):
       
        1.并查集
            顯然一堆互相聯(lián)通的小房間屬于同一個(gè)等價(jià)集 ，對(duì)二位的數(shù)據(jù)掃一遍然后映射到一
        維的并查集上求并。最后森林的個(gè)數(shù)自然就是大房間的個(gè)數(shù)了，一顆樹(shù)的重量就是房間的
        尺寸了。這個(gè)出來(lái)推墻就好辦，枚舉每一面合法的墻，兩邊的房間求一次樹(shù)根，如果不同
        根（重要細(xì)節(jié)，如果墻兩次的房間是同一個(gè)大房間的話就錯(cuò)了~）則按要求做比較。最后
        打印，收工。
       
         2.floodfill
            剛開(kāi)始我也不清楚這個(gè)做法（之前確實(shí)不知道，汗~）。后來(lái)看了下usaco的論文。
        其實(shí)還是很形象的，就是用BFS往上灌水，任何聯(lián)通的區(qū)域都會(huì)被當(dāng)前這次灌的水淹到。
        不同次灌水淹到的區(qū)域自然就是不同的大房間了。仍然不清楚的請(qǐng)看usaco上的論文。
       
         3.硬搞
            實(shí)在不會(huì)的何必想那么多呢，讓小房間構(gòu)成n*m的無(wú)向圖，沒(méi)有門(mén)的房間自然
        相鄰。直接DFS聯(lián)通分支。打印，收工。
       
        下面給出我的并查代碼的 main(),求出門(mén)的方位使用位運(yùn)算

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);   // 并查相鄰兩個(gè)房間
                                }
                                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){
                           // 從左下到右上檢查每個(gè)小房間與右、上有墻隔著的小房間，若不同根則計(jì)算

                           if(step+door[digit][0]>-1&&step2+door[digit][1]<n){  // 門(mé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;
}