做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 1480. -- 城堡【重复】

1480: 城堡【重复】

时间限制: 1 Sec  内存限制: 128 MB
提交: 17  解决: 10
[上一题][提交][讨论版][状态][下一题]

题目描述

以我们憨厚的USACO主人公农夫约翰(Farmer John) 无法想象的运气, 我们的农夫约翰在他生日那天收到了一份特别的礼物:一张“幸运爱尔兰”彩票。结果这张彩票让我们的农夫约翰获得了这次比赛唯一的奖品——坐落于爱尔兰郊外的一座梦幻般的城堡!喜欢吹嘘的农夫约翰立刻回到有着吹嘘传统的威斯康辛老家开始吹嘘了, 农夫约翰想要告诉他的奶牛们关于他的城堡的一切。他需要做一些吹嘘的准备工作:比如说知道城堡有多少个房间,每个房间有多大。而且农夫约翰想要把一个单独的墙(指两个单位间的墙)给拆掉以获得一个更大的房间。你的工作就是帮农夫约翰做吹嘘的准备,算出房间数与房间的大小。 城堡的平面图被划分成M*N(M是宽度)个正方形的单位,一个这样的单位可以有0到4面墙环绕。城堡周围一定有外墙环绕以遮风挡雨。(就是说平面图的四周一定是墙。)


请仔细研究下面这个城堡平面图(样例表示的就是此图):

这个城堡的平面图是7×4个单位的。一个“房间”指的是平面图中一个连通的“正方形单位”的集合。比如说这个样例就有5个房间(大小分别为9、7、3、1、8个单位(排名不分先后)) 。移去蓝色的那面墙(即单位(4,1)东边的墙),可以使2个房间合为一个“移掉一面单独的墙可以形成的最大的新房间”,其大小为16。


输入

城堡的平面图用一个由数字组成的矩阵表示,一个数字表示一个单位,矩阵有N行M列。输入与样例的图一致。
每一个单位的数字告诉我们这个单位的东西南北是否有墙存在。每个数字是由以下四个整数的某个或某几个或一个都没有加起来的。
1: 在西面有墙
2: 在北面有墙
4: 在东面有墙
8: 在南面有墙
城堡内部的墙会被规定两次。比如说(1,1)南面的墙,亦会被标记为(2,1)北面的墙。
第 1 行: 二个被空格分开的整数: M 和 N(N,M<=50) 。
第 2 到 N+1 行: M x N 个整数,每行M个。
城堡保证至少有2个房间,而且一定有一面墙可以被移走。

输出

输出包含以下4行:
第 1 行: 城堡的房间数目。
第 2 行: 最大的房间的大小 。
第 3 行: 移除一面墙后能得到的最大的房间的大小 。
第 4 行: 移除哪面墙 ,即要造出第三行那么大的大房间所要推倒的一面墙。
选择最佳的墙来推倒。有多解时选最西边的(还是有多解时选最南的)。用这面墙南边或西边的单位,还有这面墙在那个单位的方位("N"(北)或者"E"(东))来表示这面墙。

样例输入

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

提示

标签

[上一题][提交][讨论版][状态][下一题]