Translation

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

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

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

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

     1   2   3   4   5   6   7   ############################# 1 #   |   #   |   #   |   |   #   #####---#####---#---#####---#    2 #   #   |   #   #   #   #   #   #---#####---#####---#####---# 3 #   |   |   #   #   #   #   #      #---#########---#####---#---# 4 # ->#   |   |   |   |   #   #      #############################  # =墻壁    -,| = 沒有墻壁 -> =指向一面墻，這面墻推掉的話我們就有一間最大的新房間
友情提示，這個城堡的平面圖是7×4個單位的。一個“房間”的是平面圖中一個由“#”、“-”、“|”圍成的格子（就是圖里面的那一個個的格子）。比如說這個樣例就有5個房間。（大小分別為9、7、3、1、8個單位）
移去箭頭所指的那面墻，可以使2個房間合為一個新房間，且比移去其他墻所形成的房間都大。
城堡保證至少有2個房間，而且一定有一面墻可以被移走。
PROGRAM NAME: castle
INPUT FORMAT: 第一行有兩個整數：M和N 城堡的平面圖用一個由數字組成的矩陣表示，一個數字表示一個單位，矩陣有N行M列。輸入與樣例的圖一致。
每一個單位的數字告訴我們這個單位的東西南北是否有墻存在。每個數字是由以下四個整數的某個或某幾個加起來的(四面都沒有墻的話，這個數字應該為0)。
1: 在西面有墻2: 在北面有墻4: 在東面有墻8: 在南面有墻
城堡內部的墻會被規定兩次。比如說（1，1）南面的墻，亦會被標記為（2，1）北面的墻。
OUTPUT FORMAT:(file castle.out)
輸出包含如下4行:
第 1 行: 城堡的房間數目。
第 2 行: 最大的房間的大小
第 3 行: 移除一面墻能得到的最大的房間的大小
第 4 行: 移除哪面墻可以得到面積最大的新房間。
選擇最佳的墻來推倒。有多解時選最靠西的，仍然有多解時選最靠南的。同一格子北邊的墻比東邊的墻更優先。
用該墻的南鄰單位的北墻或西鄰單位的東墻來表示這面墻，方法是輸出鄰近單位的行數、列數和墻的方位（"N"（北）或者"E"（東））。
Solution
PS：好久沒寫代碼了，連廣搜都改了好久23333
廣搜裸題，先把數字矩陣改造成鄰接矩陣，然后廣搜得到第一二個問題的答案；隨后枚舉每一面有效的墻，廣搜計算墻被移除后的該房間面積即可。注意枚舉墻的順序
Code
#include<cstdio>#include<cstdlib>#include<algorithm>#include<cstring>using namespace std;const int maxn=50+10;int map[maxn*2][maxn*2],p[maxn*2][maxn*2],q[maxn*maxn*40][2];int dir[4][2]={{0,-1},{-1,0},{0,1},{1,0}},mod[4]={1,2,4,8};int main(){	int i,j,k,m,n,max_area=0,room_num=0,wall_x,wall_y;	freopen("castle.in","r",stdin);	freopen("castle.out","w",stdout);	scanf("%d%d",&n,&m);	for(i=2;i<=2*m;i+=2)		for(j=2;j<=2*n;j+=2){			scanf("%d",&map[i][j]);			map[i][j]=15-map[i][j];			for(k=0;k<=3;k++)				if(map[i][j]%(2*mod[k])==mod[k]){					map[i][j]-=mod[k];					map[i+dir[k][0]][j+dir[k][1]]=2;				}			map[i][j]=1;		}	for(i=2;i<=2*m;i+=2)		for(j=2;j<=2*n;j+=2){			int f=0,l=1;			int area=0;			if(!p[i][j]){				p[i][j]=1;				q[1][0]=i;q[1][1]=j;				area++;				while(f<l){					f++;					int x=q[f][0],y=q[f][1];					for(k=0;k<=3;k++)						if(map[x+dir[k][0]][y+dir[k][1]]==2 && !p[x+2*dir[k][0]][y+2*dir[k][1]]){							q[++l][0]=x+2*dir[k][0];							q[l][1]=y+2*dir[k][1];							p[x+2*dir[k][0]][y+2*dir[k][1]]=1;							area++;						}				}				if(max_area<area)max_area=area;				room_num++;			}		}	printf("%d/n%d/n",room_num,max_area);	for(j=2;j<=2*n;j++)		for(i=2*m;i>=2;i--)			if(!map[i][j] && (i+j)%2){				memset(p,0,sizeof(p));				map[i][j]=2;				int x=i,y=j;				for(k=0;k<=3;k++)					if(map[x+dir[k][0]][y+dir[k][1]]){						x+=dir[k][0];						y+=dir[k][1];						break;					}				int f=0,l=1;				int area=0;				if(!p[x][y]){					p[x][y]=1;					q[1][0]=x;q[1][1]=y;					area++;					while(f<l){						f++;						x=q[f][0],y=q[f][1];						for(k=0;k<=3;k++)							if(map[x+dir[k][0]][y+dir[k][1]]==2 && !p[x+2*dir[k][0]][y+2*dir[k][1]] && map[x+2*dir[k][0]][y+2*dir[k][1]]==1){								q[++l][0]=x+2*dir[k][0];								q[l][1]=y+2*dir[k][1];								p[x+2*dir[k][0]][y+2*dir[k][1]]=1;								area++;							}					}					if(max_area<area){						max_area=area;						wall_x=i;wall_y=j;					}					map[i][j]=0;				}			}	printf("%d/n",max_area);	if(map[wall_x+1][wall_y]==1)printf("%d %d N/n",(wall_x+1)/2,wall_y/2);	else if(map[wall_x][wall_y-1]==1)printf("%d %d E/n",wall_x/2,(wall_y-1)/2);	return 0;}