资源描述：
《usaco 2.1.1 The Castle解题报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、-------------各类专业好文档，值得你下载，教育，管理，论文，制度，方案手册，应有尽有--------------TheCastle城堡IOI'94-Day1译bytimgreen以一个几乎超乎想像的运气，农民约翰在他的生日收到了一张爱尔兰博彩的奖券。这一张奖券成为了唯一中奖的奖券。农民约翰嬴得爱尔兰的乡下地方的一个传说中的城堡。吹牛在他们威斯康辛州不算什么，农民约翰想告诉他的牛所有有关城堡的事。他想知道城堡有多少房间，而且最大的房间有多大。事实上，他想去掉一面墙来制造一个更大的房间。你的任务是帮助农民约翰去了解
2、正确房间数目和大小。城堡的平面图被分为M(wide)*N(1<=M,N<=50)个小正方形。每个这样的小正方形有0到4面墙。城堡在它的外部边缘总是有墙壁的，好遮挡风雨。考虑这注解了一个城堡的平面图： 1 2 3 4 5 6 7 ############################# 1#
3、 #
4、 #
5、
6、 # #####---#####---#---#####---# 2# #
7、 # # # # # #---#####---#####---#####---
8、# 3#
9、
10、 # # # # # #---#########---#####---#---# 4#->#
11、
12、
13、
14、 # # ##############################=墙壁-,
15、=没有墙壁->=移除这面墙能使得到的新房间最大例子的城堡的大小是7x4。一个"房间"是平面图上有连接的"小正方形"的集合。这个平面图包含五个房间。(它们的大小是9,7,3,1,和8排列没有特别的顺序)。-------------各类专业好文档，值得你下载，教育，管理，论文，制度
16、，方案手册，应有尽有---------------------------各类专业好文档，值得你下载，教育，管理，论文，制度，方案手册，应有尽有--------------移除被箭作记号的墙壁来合并两个房间来制造最大的可能房间(移除一面墙所能产生的)。城堡总是至少有二个房间并且总是有一面墙壁以可能被移除。PROGRAMNAME:castleINPUTFORMAT地图以一个表格来储存，每个数字描述一个小正方形，N行每行M个数来描述这个平面图。输入顺序符合那个在上面例子的编号方式。每个描述小正方形的数字说明小正方形的四面的墙的
17、分布情况，它是下面4个数的和：1:在西面有墙2:在北面有墙4:在东面有墙8:在南面有墙内部的墙壁是会被定义两次；小正方形(1,1)南面的墙也被指出是小正方形(2,1)北面的墙。第1行:二个被空格分开的整数:M和N第2到N+1行:MxN个整数,每行M个。SAMPLEINPUT(filecastle.in)74116116310679613515511012713751311108101213OUTPUTFORMAT输出包含一些行:第1行:城堡的房间数目。第2行:最大的房间的大小第3行:移除一面墙能得到的最大的房间的大小第4行
18、:移除哪面墙选择最佳的墙来移除，(选择最靠西的，如果仍然不能确定，再选择最靠南的。编者注：墙的位置应该由它的中点来定义)(【原文】Choosetheoptimalwalltoremovefromthesetofoptimalwallsby-------------各类专业好文档，值得你下载，教育，管理，论文，制度，方案手册，应有尽有---------------------------各类专业好文档，值得你下载，教育，管理，论文，制度，方案手册，应有尽有--------------choosingthewallfarthe
19、rtothewest(andthen,ifstilltied,farthesttothesouth).)墙壁由它在相邻的小正方形的西部或南方来命名SAMPLEOUTPUT(filecastle.out)591641E思路分析：分析图可知，每一面墙都跟它四周的房间有关，墙不用某个确定的I,j,来表示，房间可以是弯曲的，但是每一个大房间都是由小房间构成;如图所以用floodfill染色即可；开始根据二进制的特点处理每个方格四个方向上的墙是否存在；最后在跟据染成的颜色找出要推倒的墙；程序参考nocow如下{ID:zhaicon2
20、PROG:castleLANG:PASCAL}programcastle;constd:array[1..4]oflongint=(1,2,4,8);//都是方向dx:array[1..4]oflongint=(0,-1,0,1);dy:array[1..4]oflongint=(-1,0,1,0);v
