我们憨厚的USACO主人公农夫约翰(Farmer John)以无法想象的运气,在他生日那天收到了一份特别的礼物：一张“幸运爱尔兰”（一种彩票）。结果这张彩票让他获得了这次比赛唯一的奖品——坐落于爱尔兰郊外的一座梦幻般的城堡！(RP...)
喜欢吹嘘的农夫约翰立刻回到有着吹嘘传统的威斯康辛老家开始吹嘘了, 农夫约翰想要告诉他的奶牛们关于他城堡的一切。他需要做一些吹嘘前的准备工作：比如说知道城堡有多少个房间，每个房间有多大。另外，农夫约翰想要把一面单独的墙（指两个单位间的墙）拆掉以形成一个更大的房间。你的工作就是帮农夫约翰做以上的准备，算出房间数与房间的大小。
城堡的平面图被划分成M*N（M是宽度）个正方形的单位，一个这样的单位可以有0到4面墙环绕。城堡周围一定有外墙环绕以遮风挡雨。（就是说平面图的四周一定是墙。）
请仔细研究下面这个有注解的城堡平面图：
1 2 3 4 5 6 7
#############################
1 # | # | # | | #
#####---#####---#---#####---#
2 # # | # # # # #
#---#####---#####---#####---#
3 # | | # # # # #
#---#########---#####---#---#
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个房间，而且一定有一面墙可以被移走。
格式
PROGRAM NAME: castle
INPUT FORMAT: 城堡的平面图用一个由数字组成的矩阵表示，一个数字表示一个单位，矩阵有N行M列。输入与样例的图一致。
每一个单位的数字告诉我们这个单位的东西南北是否有墙存在。每个数字是由以下四个整数的某个或某几个或一个都没有加起来的。
1: 在西面有墙
2: 在北面有墙
4: 在东面有墙
8: 在南面有墙
城堡内部的墙会被规定两次。比如说（1，1）南面的墙，亦会被标记为（2，1）北面的墙。
(file castle.in)
第 1 行: 二个被空格分开的整数: M 和 N（N,M<=50）
第 2 到 N+1 行: M x N 个整数,每行M个。
OUTPUT FORMAT:
(file castle.out)
输出包含如下4行:
第 1 行: 城堡的房间数目。
第 2 行: 最大的房间的大小
第 3 行: 移除一面墙能得到的最大的房间的大小
第 4 行: 移除哪面墙
要造出第三行那么大的大房间所要推倒的一面墙。
选择最佳的墙来推倒。有多解时选最西边的（仍然有多解时选这些里面最南的）。用这面墙南边或西边的单位，还有这面墙在那个单位的方位（"N"（北）或者"E"（东））来表示这面墙。
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
【参考程序】：
/*
ID: XIONGNA1
PROG: castle
LANG: C++
*/
#include<iostream>
#include<cstring>
using namespace std;
const int dn[5]={0,1,2,4,8};
const int dx[5]={0,0,-1,0,1};
const int dy[5]={0,-1,0,1,0};
bool wall[51][51][5];
int area[2501],code[51][51];
int n,m;
bool check(int x,int y)
{
if (x>=1 && x<=m && y>=1 && y<=n)
return true;
return false;
}
void floodfill(int x,int y,int c)
{
area[c]++;code[x][y]=c;
int tx,ty;
for (int i=1;i<=4;i++)
if (wall[x][y][i])
{
tx=x+dx[i]; ty=y+dy[i];
if (check(tx,ty) && (code[tx][ty]==0))
floodfill(tx,ty,c);
}
}
int main()
{
freopen("castle.in","r",stdin);
freopen("castle.out","w",stdout);
scanf("%d%d",&n,&m);
memset(wall,true,sizeof(wall));
int s;
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
{
scanf("%d",&s);
for (int k=4;k>=1;k--)
if (s>=dn[k])
{
s-=dn[k];
wall[i][j][k]=false;
}
}
memset(code,0,sizeof(code));
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
if (code[i][j]==0)
{
s++;
floodfill(i,j,s);
}
printf("%d\n",s);
int max1=0;
for (int i=1;i<=s;i++)
if (area[i]>max1) max1=area[i];
printf("%d\n",max1);
max1=0; int r1,r2,r3,x1,y1;
for (int j=1;j<=n;j++)
for (int i=m;i>=1;i--)
for (int k=2;k<=3;k++)
{
x1=i+dx[k]; y1=j+dy[k];
if (check(x1,y1) && (code[i][j]!=code[x1][y1]))
if (area[code[x1][y1]]+area[code[i][j]]>max1)
{
max1=area[code[x1][y1]]+area[code[i][j]];
r1=i;r2=j;r3=k;
}
}
printf("%d\n%d %d ",max1,r1,r2);
if (r3==2) printf("N\n");
else printf("E\n");
return 0;
}