本文介绍了USACO竞赛中的一道题目——The Castle，内容涉及通过输入的城堡平面图计算房间数量、最大房间大小及可合并的最大房间。解题思路包括使用DFS遍历和标记房间，并详细解释了如何确定最佳移除的墙壁。
题目描述
以一个几乎超乎想像的运气，农民约翰在他的生日收到了一张爱尔兰博彩的奖券。
这一张奖券成为了唯一中奖的奖券。
农民约翰嬴得爱尔兰的乡下地方的一个传说中的城堡。
吹牛在他们威斯康辛州不算什么，农民约翰想告诉他的牛所有有关城堡的事。
他想知道城堡有多少房间，而且最大的房间有多大。
事实上，他想去掉一面墙来制造一个更大的房间。
你的任务是帮助农民约翰去了解正确房间数目和大小。
城堡的平面图被分为 M(wide)*N(1 <=M,N<=50)个小正方形。
每个这样的小正方形有0到4面墙。
城堡在它的外部边缘总是有墙壁的，好遮挡风雨。
考虑这注解了一个城堡的平面图：
例子的城堡的大小是7 x 4。
一个 "房间"是平面图上有连接的"小正方形"的集合。
这个平面图包含五个房间。(它们的大小是9,7,3,1, 和 8 排列没有特别的顺序)。
移除被箭作记号的墙壁来合并两个房间来制造最大的可能房间(移除一面墙所能产生的)。
城堡总是至少有二个房间并且总是有一面墙壁以可能被移除。
输入
从文件 castle.in 中读入数据。
地图以一个表格来储存，每个数字描述一个小正方形，N行每行M个数来描述这个平面图。
输入顺序符合那个在上面例子的编号方式。
每个描述小
最低0.47元/天 解锁文章
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
