##前言
由于這道題比較難，有不好描述，我就直接貼題目了。

##Description
以一個(gè)幾乎超乎想像的運(yùn)氣，農(nóng)民約翰在他的生日收到了一張愛(ài)爾蘭博彩的獎(jiǎng)券。
這一張獎(jiǎng)券成為了唯一中獎(jiǎng)的獎(jiǎng)券。
農(nóng)民約翰嬴得愛(ài)爾蘭的鄉(xiāng)下地方的一個(gè)傳說(shuō)中的城堡。
吹牛在他們威斯康辛州不算什么，農(nóng)民約翰想告訴他的牛所有有關(guān)城堡的事。
他想知道城堡有多少房間，而且最大的房間有多大。
事實(shí)上，他想去掉一面墻來(lái)制造一個(gè)更大的房間。
你的任務(wù)是幫助農(nóng)民約翰去了解正確房間數(shù)目和大小。
城堡的平面圖被分為 M(wide)*N(1 <=M,N<=50)個(gè)小正方形。
每個(gè)這樣的小正方形有0到4面墻。
城堡在它的外部邊緣總是有墻壁的，好遮擋風(fēng)雨。
考慮這注解了一個(gè)城堡的平面圖：

例子的城堡的大小是7 x 4。
一個(gè) "房間"是平面圖上有連接的"小正方形"的集合。
這個(gè)平面圖包含五個(gè)房間。(它們的大小是9,7,3,1, 和 8 排列沒(méi)有特別的順序)。
移除被箭作記號(hào)的墻壁來(lái)合并兩個(gè)房間來(lái)制造最大的可能房間(移除一面墻所能產(chǎn)生的)。
城堡總是至少有二個(gè)房間并且總是有一面墻壁以可能被移除。

###Input
地圖以一個(gè)表格來(lái)儲(chǔ)存，每個(gè)數(shù)字描述一個(gè)小正方形，N行每行M個(gè)數(shù)來(lái)描述這個(gè)平面圖。
輸入順序符合那個(gè)在上面例子的編號(hào)方式。
每個(gè)描述小正方形的數(shù)字說(shuō)明小正方形的四面的墻的分布情況，它是下面4個(gè)數(shù)的和：
1: 在西面有墻
2: 在北面有墻
4: 在東面有墻
8: 在南面有墻
內(nèi)部的墻壁是會(huì)被定義兩次；小正方形(1,1)南面的墻也被指出是小正方形(2,1)北面的墻。
第 1 行: 二個(gè)被空格分開(kāi)的整數(shù): M 和 N
第 2 到 N+1 行: M x N 個(gè)整數(shù),每行M個(gè)。

###Output
輸出包含一些行:
第 1 行: 城堡的房間數(shù)目。
第 2 行: 最大的房間的大小
第 3 行: 移除一面墻能得到的最大的房間的大小
第 4 行: 移除哪面墻
選擇最佳的墻來(lái)移除，(選擇最靠西的，如果仍然不能確定，再選擇最靠南的。編者注：墻的位置應(yīng)該由它的中點(diǎn)來(lái)定義)
(【原文】Choose the optimal wall to remove from the set of optimal walls by choosing the wall farther to the west (and then, if still tied, farthest to the south).)
墻壁由它在相鄰的小正方形的西部或南方來(lái)命名
最后一行一定要有回車(chē)

###Sample Input
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

###Sample Output
5
9
16
4 1 E

---

##解題思路
用廣搜求出前2個(gè)值。求出每個(gè)小方格的對(duì)應(yīng)的房間的大小，然后枚舉一下破壞哪堵墻求最大值。

---

##代碼

#include<cstdio> #include<iostream> using namespace std; const int W=0,N=1,E=2,S=3;//常量 int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0}; //搜索方向 bool a[51][51][4];//記錄有沒(méi)有墻 int head,tail,walk[51][51],ft[2501],mn,maxs,x,n,m; int state[2501][2],c; void bfs(int x,int y) {c++;//標(biāo)記房間號(hào)head=0;tail=1;state[1][0]=x;state[1][1]=y;walk[x][y]=c;//初始化do{head+=1;for (int i=0;i<4;i++) {x=state[head][0]+dx[i];y=state[head][1]+dy[i];int zx,zy;zx=state[head][0];zy=state[head][1];if (walk[x][y]==0 && !a[zx][zy][i] && x<=n && y<=m && x>=1 && y>=1){tail++;state[tail][0]=x;state[tail][1]=y;walk[x][y]=c;//歸入當(dāng)前房間}}}while (head<tail); } int main() {scanf("%d%d",&m,&n); for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){scanf("%d",&x);if (x>=8) {a[i][j][S]=true;a[i+1][j][N]=true;x-=8;}//南墻if (x>=4) {a[i][j][E]=true;a[i][j+1][W]=true;x-=4;}//東墻if (x>=2) {a[i][j][N]=true;a[i-1][j][S]=true;x-=2;}//北墻if (x>=1) {a[i][j][W]=true;a[i][j-1][E]=true;x-=1;}//西墻} for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)if (!walk[i][j]){mn++;//房間總數(shù)bfs(i,j);//搜索maxs=max(maxs,tail);//求最大房間ft[c]=tail;//記錄房間大小}printf("%d\n%d\n",mn,maxs);//輸出maxs=0;x=0;int y=0;char wall='0';//根據(jù)題目要求我們可以得知只有可能破壞N或E墻for (int j=1;j<=m;j++)for (int i=n;i>=1;i--) {if (i-1>=1 && a[i][j][N] && walk[i][j]!=walk[i-1][j] && ft[walk[i][j]]+ft[walk[i-1][j]]>maxs)//判斷如果該方向有墻而且不屬于同一個(gè)房間{maxs=ft[walk[i][j]]+ft[walk[i-1][j]];x=i;y=j;wall='N';}//同上if (j+1<=m && a[i][j][E] && walk[i][j]!=walk[i][j+1] && ft[walk[i][j]]+ft[walk[i][j+1]]>maxs){maxs=ft[walk[i][j]]+ft[walk[i][j+1]];x=i;y=j;wall='E';}}printf("%d\n%d %d %c",maxs,x,y,wall); }

總結(jié)

以上是生活随笔為你收集整理的ssl1104-USACO 2.1城堡(foodfill)【图论,广搜】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。