1020. 【USACO题库】2.1.1 The Castle城堡

题目描述

以一个几乎超乎想像的运气,农民约翰在他的生日收到了一张爱尔兰博彩的奖券。

这一张奖券成为了唯一中奖的奖券。

农民约翰嬴得爱尔兰的乡下地方的一个传说中的城堡。

吹牛在他们威斯康辛州不算什么,农民约翰想告诉他的牛所有有关城堡的事。

他想知道城堡有多少房间,而且最大的房间有多大。

事实上,他想去掉一面墙来制造一个更大的房间。
你的任务是帮助农民约翰去了解正确房间数目和大小。

城堡的平面图被分为 M(wide)*N(1 <=M,N<=50)个小正方形。

每个这样的小正方形有0到4面墙。

城堡在它的外部边缘总是有墙壁的,好遮挡风雨。
考虑这注解了一个城堡的平面图:




例子的城堡的大小是7 x 4。
一个 "房间"是平面图上有连接的"小正方形"的集合。

这个平面图包含五个房间。(它们的大小是9,7,3,1, 和 8 排列没有特别的顺序)。
移除被箭作记号的墙壁来合并两个房间来制造最大的可能房间(移除一面墙所能产生的)。

城堡总是至少有二个房间并且总是有一面墙壁以可能被移除。

输入

从文件 castle.in 中读入数据。

地图以一个表格来储存,每个数字描述一个小正方形,N行每行M个数来描述这个平面图。

输入顺序符合那个在上面例子的编号

相关推荐

  1. USACO 2024 Jan B题解

    2024-05-05 05:58:09       37 阅读
  2. USACO21JAN Minimum Cost Paths P

    2024-05-05 05:58:09       43 阅读
  3. PYTHON 120题目详解(100-102

    2024-05-05 05:58:09       24 阅读
  4. 题解】洛谷 P9183 [USACO23OPEN] FEB B

    2024-05-05 05:58:09       39 阅读
  5. P1697 [USACO18JAN] Lifeguards B 题解

    2024-05-05 05:58:09       28 阅读
  6. P1596 [USACO10OCT] Lake Counting S 题解

    2024-05-05 05:58:09       11 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-05-05 05:58:09       18 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-05-05 05:58:09       19 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-05-05 05:58:09       18 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-05-05 05:58:09       20 阅读

热门阅读

  1. 项目表(31-40)

    2024-05-05 05:58:09       8 阅读
  2. Python实战开发及案例分析(2)——单目标优化

    2024-05-05 05:58:09       11 阅读
  3. Scala 补充 正则、异常处理...

    2024-05-05 05:58:09       9 阅读
  4. 【Python】数据类型

    2024-05-05 05:58:09       10 阅读
  5. vue key的原理和作用

    2024-05-05 05:58:09       7 阅读
  6. 函数的引用参数

    2024-05-05 05:58:09       7 阅读
  7. C# 中 IOC (Inversion of Control,控制反转)

    2024-05-05 05:58:09       9 阅读