题目描述

以一个几乎超乎想像的运气,农民约翰在他的生日收到了一张爱尔兰博彩的奖券.这一张奖券成为

了唯一中奖的奖券.农民约翰嬴得爱尔兰的乡下地方的一个传说中的城堡.

吹牛在他们威斯康辛州不算什么,农民约翰想告诉他的牛所有有关城堡的事.他想知道城堡有多少

房间,而且最大的房间有多大.事实上,他想去掉一面墙来制造一个更大的房间.

你的任务是帮助农民约翰去了解正确房间数目和大小.城堡的平面图被分为 M(wide)*N(1 <=M,N<=50)个小正方形.

每个这样的小正方形有0到4 面墙.城堡在它的外部边缘总是有墙壁的,好遮挡风雨.

考虑这注解了一个城堡的平面图:

1 2 3 4 5 6 7

#############################

1 # | # | # | | #

#####---#####---#---#####---#

2 # # | # # # # #

#---#####---#####---#####---#

3 # | | # # # # #

#---#########---#####---#---#

4 # -># | | | | # #

#############################

# =墙壁 -, | = 没有墙壁

-> =移除这面墙能使得到的新房间最大

例子的城堡的大小是 7 x 4.

一个 "房间"是平面图上有连接的"小正方形"的集合.

这个平面图包含五个房间.(它们的大小是 9,7,3,1, 和 8 排列没有特别的顺序).

移除被箭作记号的墙壁来合并两个房间来制造最大的可能房间(移除一面墙所能产生的).

城堡总是至少有二个房间并且总是有一面墙壁以可能被移除.

PROGRAM NAME: castle

INPUT FORMAT

地图以一个表格来储存,每个数字描述一个小正方形,N 行每行 M 个数来描述这个平面图.

输入顺序符合那个在上面例子的编号方式.

每个描述小正方形的数字说明小正方形的四面的墙的分布情况,它是下面 4 个数的和:

1: 在西面有墙

2: 在北面有墙

214: 在东面有墙

8: 在南面有墙

内部的墙壁是会被定义两次；小正方形(1,1)南面的墙也被指出是小正方形(2,1)北面的墙.

第 1 行: 二个被空格分开的整数: M 和 N

第 2 到: N+1 行: M x N 个整数,每行 M 个.

SAMPLE INPUT (file castle.in)

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

OUTPUT FORMAT

输出包含一些行:

第 1 行: 城堡的房间数目.

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

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

第 4 行: 移除哪面墙

选择最佳的墙来移除,(选择最靠西的,如果仍然不能确定,再选择最靠南的.编者注:墙的位置应该

由它的中点来定义)

墙壁由它在相邻的小正方形的西部或南方来命名

SAMPLE OUTPUT (file castle.out)

5

9

16

4 1 E