2.1.1The Castle城堡

2020年1月17日 1010点热度 0人点赞 0条评论

2.1.1The Castle城堡

时间: 1ms        内存:64M

描述:

我们憨厚的USACO主人公农夫约翰(Farmer John)以无法想象的运气,在他生日那天收到了一份特别的礼物:一张“幸运爱尔兰”(一种彩票)。结果这张彩票让他获得了这次比赛唯一的奖品——坐落于爱尔兰郊外的一座梦幻般的城堡!

喜欢吹嘘的农夫约翰立刻回到有着吹嘘传统的威斯康辛老家开始吹嘘了, 农夫约翰想要告诉他的奶牛们关于他城堡的一切。他需要做一些吹嘘前的准备工作:比如说知道城堡有多少个房间,每个房间有多大。另外,农夫约翰想要把一面单独的墙(指两个单位间的墙)拆掉以形成一个更大的房间。你的工作就是帮农夫约翰做以上的准备,算出房间数与房间的大小。

城堡的平面图被划分成M*N(1 <=M,N<=50)个正方形的单位,一个这样的单位可以有0到4面墙环绕。城堡周围一定有外墙环绕以遮风挡雨。(就是说平面图的四周一定是墙。) 请仔细研究下面这个有注解的城堡平面图:

 1   2   3   4   5   6   7
  #############################
1 #   |   #   |   #   |   |   #
  #####---#####---#---#####---#   
2 #   #   |   #   #   #   #   #
  #---#####---#####---#####---#
3 #   |   |   #   #   #   #   #   
  #---#########---#####---#---#
4 # ->#   |   |   |   |   #   #   
  #############################

# =墙壁 -,| = 没有墙壁
-> =指向一面墙,这面墙推掉的话我们就有一间最大的新房间

友情提示,这个城堡的平面图是7×4个单位的。一个“房间”指的是平面图中一个连通的“正方形单位”的集合。比如说这个样例就有5个房间。(大小分别为9、7、3、1、8个单位(排名不分先后))

移去箭头所指的那面墙,可以使2个房间合为一个新房间,且比移去其他墙所形成的房间都大。(原文为:Removing the wall marked by the arrow merges a pair of rooms to make the largest possible room that can be made by removing a single wall. )

城堡保证至少有2个房间,而且一定有一面墙可以被移走。

输入:

城堡的平面图用一个由数字组成的矩阵表示,一个数字表示一个单位,矩阵有N行M列。输入与样例的图一致。

每一个单位的数字告诉我们这个单位的东西南北是否有墙存在。每个数字是由以下四个整数的某个或某几个或一个都没有加起来的。

1: 在西面有墙
2: 在北面有墙
4: 在东面有墙
8: 在南面有墙

城堡内部的墙会被规定两次。比如说(1,1)南面的墙,亦会被标记为(2,1)北面的墙。

输出:

输出包含如下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

提示:

参考答案:

解锁文章

没有看到答案?微信扫描二维码可免费解锁文章

微信扫描二维码解锁

使用微信扫描二维码打开广告页面后可以立即关闭,再刷新此页面即可正常浏览此文章

所跳转广告均由第三方提供,并不代表本站观点!

已经扫描此二维码?点此立即跳转

code

这个人很懒,什么都没留下

文章评论