提示: 欢迎访问OurACM平台。
Problem 1552 猪的城堡

Accept: 63    Submit: 250
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

以一个极佳的人品,猪老大在它的生日收到了一张奖券。它嬴得乡下地方的一个传说中的城堡。猪老大想告诉它的猪手下所有有关城堡的事。

它想知道城堡有多少房间,而且最大的房间有多大。

事实上,它想去掉一面墙来制造一个更大的房间。
你的任务是帮助猪老大去了解正确房间数目和大小。
城堡的平面图被分为 M(宽)*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 排列没有特别的顺序)。

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

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

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

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

每个描述小正方形的数字说明小正方形的四面的墙的分布情况,它是下面4个数的和:
1: 在西面有墙
2: 在北面有墙
4: 在东面有墙
8: 在南面有墙

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

Input

输入包含多组测试数据,请处理到EOF结束。
每组数据包括:
第 1 行:二个被空格分开的整数: M 和 N
第 2 到 N+1 行:M x N 个整数,每行M个。

Output

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

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

Source

ACM模拟赛之再见猪年

Submit  Back  Status  Discuss