2428: 城堡

以一个几乎超乎想像的运气,农民约翰在他的生日收到了一张爱尔兰博彩的奖券.这一张奖券成为 了唯一中奖的奖券.农民约翰嬴得爱尔兰的乡下地方的一个传说中的城堡. 吹牛在他们威斯康辛州不算什么,农民约翰想告诉他的牛所有有关城堡的事.他想知道城堡有多少 房间,而且最大的房间有多大.事实上,他想去掉一面墙来制造一个更大的房间. 你的任务是帮助农民约翰去了解正确房间数目和大小. 城堡的平面图被分为 M(wide)*N(1 <=M,N<=50)个小正方形. 每个这样的小正方形有0到4 面墙. 城堡在它的外部边缘总是有墙壁的,好遮挡风雨. 考虑这注解了一个城堡的平面图:

# =墙壁 -
| = 没有墙壁
-> =移除这面墙能使得到的新房间最大
例子的城堡的大小是 7 x 4. 一个 "房间"是平面图上有连接的"小正方形"的集合. 这个平面图包含五个房间.(它们的大小是 9,7,3,1, 和 8 排列没有特别的顺序). 移除被箭作记号的墙壁来合并两个房间来制造最大的可能房间(移除一面墙所能产生的). 城堡总是至少有二个房间并且总是有一面墙壁以可能被移除.

地图以一个表格来储存,每个数字描述一个小正方形,N 行每行 M 个数来描述这个平面图. 输入顺序符合那个在上面例子的编号方式. 每个描述小正方形的数字说明小正方形的四面的墙的分布情况,它是下面 4 个数的和:
1: 在西面有墙
2: 在北面有墙
4: 在东面有墙
8: 在南面有墙
内部的墙壁是会被定义两次；小正方形(1,1)南面的墙也被指出是小正方形(2,1)北面的墙.
第 1 行: 二个被空格分开的整数: M 和 N
第 2 行: N+1 行: M x N 个整数,每行 M 个.

输出包含一些行:
第 1 行: 城堡的房间数目.
第 2 行: 最大的房间的大小
第 3 行: 移除一面墙能得到的最大的房间的大小
第 4 行: 移除哪面墙
选择最佳的墙来移除,(选择最靠西的,如果仍然不能确定,再选择最靠南的.编者注:墙的位置应该由它的中点来定义) 墙壁由它在相邻的小正方形的西部或南方来命名

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

5
9
16
4 1 E