问题 12: 送时间 [Damon Doucet,2010年]
贝西的喂养时间和农民约翰正试图决定把她放在哪儿。校有一个农场,它包括宽 x 高 (1<= w="">=><=
>=
>750.1<= h="">=><= 750) squares and is partitioned into one or more
750)="" squares="" and="" is="" partitioned="" into="" one="" or="" more="">= 750) squares and is partitioned into one or more
>大、 小岩分隔的牧场。每个牧场包含一些草和一些岩石。
贝西是饿了的小母牛,只是爱吃,吃,吃她草。她可以移到任何其他方的任何广场水平、 垂直方向,或沿对角线方向相邻。贝茜不能交叉岩石因为他们伤害了她的脚,当然,她不能离开农场。贝西想要知道方块的最大数量她能吃的草。
校有他的农场的地图哪里一个 ' ' 表示一个正方形的草,和一个 '*' 表示一个岩石。这 10 x 8 张地图和详细的考虑每个及其三个牧场的程度的分项数字:
...*....** | 111*....** ...*2222** ...*....**..**....** | 11**....** ..** 2222年 ****....**...*....** | 111*....** ...*2222** ...*....**...**.*.** | 111**.*.** ...**2*2** ...**.*.*****.**.*** | ***1**.*** ***.**2*** ***.**.***...**.*.** | 111**.*.** ...**2*2** ...**.*.**...*.***** | 111*.***** ...*2***** ...*.*****...***..** | 111***..** ...***..** ...***33**
牧场 1 有 21 平方 ; 牧场 2 18 平方 ; 牧场 3 已2 平方。因此贝应选择,其中 21 方块 1 牧场最大限度地她能吃的草。
问题产品名称: feedtime
输入格式:
* 第 1 行: 两个空格分隔整数: W 和 H
* 线 2..H + 1: 我 + 1 描述了字段的线行我用宽字符 (和没有空格) 每个或者 ' ' * '
INPUT 示例 (feedtime.in 文件):
10 8...*....**..**....**...*....**...**.*.*****.**.***...**.*.**...*.*****...***..**
输出格式:
* 第 1 行: 为一个整数,它表示的最大数量贝西可以吃的草的平方。
示例输出 (feedtime.out 文件):
21