城堡(The Castle)ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【题目描述】
以一个几乎超乎想像的运气，农民约翰在他的生日收到了一张爱尔兰博彩的奖券。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
这一张奖券成为了唯一中奖的奖券。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
农民约翰嬴得爱尔兰的乡下地方的一个传说中的城堡。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
吹牛在他们威斯康辛州不算什么，农民约翰想告诉他的牛所有有关城堡的事。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
他想知道城堡有多少房间，而且最大的房间有多大。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
事实上，他想去掉一面墙来制造一个更大的房间。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
你的任务是帮助农民约翰去了解正确房间数目和大小。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
城堡的平面图被分为 M(wide)*N(1 <=M,N<=50)个小正方形。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
每个这样的小正方形有0到4面墙。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
城堡在它的外部边缘总是有墙壁的，好遮挡风雨。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
考虑这注解了一个城堡的平面图：ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 2 3 4 5 6 7
#############################
1 # | # | # | | #
#####---#####---#---#####---#
2 # # | # # # # #
#---#####---#####---#####---#
3 # | | # # # # #
#---#########---#####---#---#
4 # -># | | | | # #
#############################
#为墙壁 -,|为没有墙壁
-> 为移除这面墙能使得到的新房间最大
ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
例子的城堡的大小是7 x 4。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
一个 "房间"是平面图上有连接的"小正方形"的集合。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
这个平面图包含五个房间。(它们的大小是9,7,3,1, 和 8 排列没有特别的顺序)。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
移除被箭作记号的墙壁来合并两个房间来制造最大的可能房间(移除一面墙所能产生的)。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
城堡总是至少有二个房间并且总是有一面墙壁以可能被移除。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输入】
地图以一个表格来储存，每个数字描述一个小正方形，N行每行M个数来描述这个平面图。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入顺序符合那个在上面例子的编号方式。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
每个描述小正方形的数字说明小正方形的四面的墙的分布情况，它是下面4个数的和：ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1: 在西面有墙ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2: 在北面有墙ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
4: 在东面有墙ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
8: 在南面有墙ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
内部的墙壁是会被定义两次；小正方形(1,1)南面的墙也被指出是小正方形(2,1)北面的墙。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第 1 行:二个被空格分开的整数: M 和 NymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第 2 到 N+1 行:M x N 个整数,每行M个。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输出】
输出包含一些行:ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第 1 行:城堡的房间数目。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第 2 行:最大的房间的大小ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第 3 行:移除一面墙能得到的最大的房间的大小ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第 4 行:移除哪面墙ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
选择最佳的墙来移除，(选择最靠西的，如果仍然不能确定，再选择最靠南的)ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
(【原文】Choose the optimal wall to remove from the set of optimal walls by choosing the wall farther to the west (and then, if still tied, farthest to the south).)ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
墙壁由它在相邻的小正方形的西部或南方来命名。ymA100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输入样例】
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
