題目描述
我們憨厚的USACO主人公農夫約翰(Farmer John)以無法想象的運氣,在他生日那天收到了一份特別的禮物：一張“幸運愛爾蘭”（一種彩票）。結果這張彩票讓他獲得了這次比賽唯一的獎品——坐落于愛爾蘭郊外的一座夢幻般的城堡！

喜歡吹噓的農夫約翰立刻回到有著吹噓傳統的威斯康辛老家開始吹噓了, 農夫約翰想要告訴他的奶牛們關于他城堡的一切。他需要做一些吹噓前的準備工作：比如說知道城堡有多少個房間，每個房間有多大。另外，農夫約翰想要把一面單獨的墻（指兩個單位間的墻）拆掉以形成一個更大的房間。 你的工作就是幫農夫約翰做以上的準備，算出房間數與房間的大小。

城堡的平面圖被劃分成M*N(1 <=M,N<=50）個正方形的單位，一個這樣的單位可以有0到4面墻環繞。城堡周圍一定有外墻環繞以遮風擋雨。（就是說平面圖的四周一定是墻。）

請仔細研究下面這個有注解的城堡平面圖：

友情提示，這個城堡的平面圖是7×4個單位的。一個“房間”的是平面圖中一個由“#”、“-”、“|”圍成的格子（就是圖里面的那一個個的格子）。比如說這個樣例就有5個房間。（大小分別為9、7、3、1、8個單位（排名不分先后））

移去箭頭所指的那面墻，可以使2個房間合為一個新房間，且比移去其他墻所形成的房間都大。（原文為：Removing the wall marked by the arrow merges a pair of rooms to make the largest possible room that can be made by removing a single wall. ）

城堡保證至少有2個房間，而且一定有一面墻可以被移走。

輸入輸出格式
輸入格式：
第一行有兩個整數：M和N 城堡的平面圖用一個由數字組成的矩陣表示，一個數字表示一個單位，矩陣有N行M列。輸入與樣例的圖一致。

每一個單位的數字告訴我們這個單位的東西南北是否有墻存在。每個數字是由以下四個整數的某個或某幾個或一個都沒有加起來的。

1: 在西面有墻

2: 在北面有墻

4: 在東面有墻

8: 在南面有墻

城堡內部的墻會被規定兩次。比如說（1，1）南面的墻，亦會被標記為（2，1）北面的墻。

輸出格式：
輸出包含如下4行:

第 1 行: 城堡的房間數目。

第 2 行: 最大的房間的大小

第 3 行: 移除一面墻能得到的最大的房間的大小

第 4 行: 移除哪面墻可以得到面積最大的新房間。

選擇最佳的墻來推倒。有多解時選最靠西的，仍然有多解時選最靠南的。同一格子北邊的墻比東邊的墻更優先。

用該墻的南鄰單位的北墻或西鄰單位的東墻來表示這面墻，方法是輸出鄰近單位的行數、列數和墻的方位（“N”（北）或者"E"（東））。

輸入輸出樣例
輸入樣例#1：
7 4
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13
輸出樣例#1：
5
9
16
4 1 E
說明
USACO 2.1

翻譯來自NOCOW

這個題就是怎么拆一面墻使的房間面積最大，這里有一個坑，就是最大的房間不一定是兩間房的和，畢竟好幾間房相連，有時候會比大房子大！

#include <bits/stdc++.h> using namespace std; int n,m,h[55][55],a[55][55][4],s,ans,z1,z2; int q1[10010],q2[10010],f[10010]; int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0}; char z3; string z="WNEA"; int main(){cin>>m>>n;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int x;cin>>x;if(x&1)a[i][j][0]=1;if(x&2)a[i][j][1]=1;if(x&4)a[i][j][2]=1;if(x&8)a[i][j][3]=1;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!h[i][j]){int front=0,rear=1,sum=1;q1[1]=i;q2[1]=j;h[i][j]=++s;while(front<rear){front++;int x=q1[front],y=q2[front];for(int k=0;k<=3;k++){int tx=x+dx[k],ty=y+dy[k];if(tx>0&&tx<=n&&ty>0&&ty<=m&&!h[tx][ty]&&!a[x][y][k]){h[tx][ty]=s;sum++;q1[++rear]=tx;q2[rear]=ty;}}}ans=max(ans,sum);f[s]=sum;}cout<<s<<endl<<ans<<endl;for(int j=1;j<=m;j++)for(int i=n;i>=1;i--)for(int k=1;k<=2;k++)if(a[i][j][k]){int tx=i+dx[k],ty=j+dy[k];int x=f[h[tx][ty]]+f[h[i][j]];if(x>ans&&h[tx][ty]!=h[i][j]){ans=x;z1=i;z2=j;z3=z[k];}}cout<<ans<<endl<<z1<<" "<<z2<<" "<<z3;return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的P1457 城堡 The Castle 位运算+BFS+思维（难题，好题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。