← 返回题目列表

AtCoder · tenka1_2012_12

D. 于宾雅的花园

中文机器翻译题面 查看原题

問題文

一个妖精们居住的村庄。
図 1 是妖精村的示例。妖精村呈由方格组成的长方形形状,由房屋、空地和树木构成。

図 1:妖精村的示例

村里有一位负责走访每个妖精的房屋并投递邮件的妖精,名叫“邮递员”。
邮递员在投递邮件时必须遵守以下 5 条规则。

  1. 必须将邮件送到村庄中所有的房屋。
  2. 不能经过树木,只能经过空地和房屋。此外,不能走出村庄。
  3. 投递时经过的空地可以多次经过同一个地点。
  4. 相邻的东西南北 4 四个方向中,只能从空地所在的位置进入房屋。
  5. 房屋的进出 1 只能从一个方向进行。也就是说,不能穿过房屋。

例如,举出一条邮递员用于投递的路线, 1 条路线就是图 2(a) 中的橙色线。
此时,根据不能穿过房屋这一规则,图 2(b) 所示的投递路线违反了规则。

図 2(a):投递路线示例 2(b):违反规则的投递路线

现在,仙女们都爱花,所以我想把玉宾雅送货路线外的所有空地都变成花园。
回答当时花园中可以创建的最大方块数。
如果没有符合规则的配送路线, 回答 -1 。


入力

输入是按以下格式从标准输入给出的。
H W
c_{(0,0)}c_{(1,0)}‥‥c_{(W-1,0)}
c_{(0,1)}c_{(1,1)}‥‥c_{(W-1,1)}
:
:
c_{(0,H-1)}c_{(1,H-1)}‥‥c_{(W-1,H-1)}
  • 输入是 H+1 。
  • 1 第一行包含一个整数,表示矩形仙村的南北距离。 H(4≤H≤10) 和一个代表东西距离的整数 W(4≤W≤10) 作为空格分隔符给出。
  • 2 从线 H 行中,每一行都显示了仙村每个方格的土地使用状况。 c_{(i,j)}(0≤i≤W-1, 0≤j≤H−1) 是 在 W 逐个字符给出。
    • c_{(i,j)} 是以下其中一项,均来自西边。 从北数第 i+1 从北方 j+1 代表第 格的土地。
      • H :表示该广场的土地上有一座房子。
      • # :表示该方格内有一棵树。
      • . :表示该广场为空地。
    • 仙女村的房屋总数为 3 以上 W×H 下面。

出力

输入仙村面积较小 如果只有 (W=4, H=4) 是正确的,100 部分积分换满分 50 点。 如果您正确回答了所有满足

出力

当配送路线以外的空地变成花园时,花园中的方格数的最大值将作为标准输出输出。 1 行。
但是,如果没有合规的配送路线, 输出 -1 。 请在末尾输出换行符。

入力例 1

4 4
...H
#H..
...#
H..H

出力例 1

5
  • 如果创建了如下图所示的花园,则配送路线可以遵循规则,花园将会 将会有 5 块。

入力例 2

4 4
....
....
.HHH
....

出力例 2

10
  • 即使房屋彼此相邻,您也无法在房屋之间直接移动。
  • 因此,房屋北侧的空地 3 南侧空地 3 由于不能在 10 块。

入力例 3

4 4
...H
.#.#
.#.#
H#.H
更正:2012/08/29 19:40 右上角的H改为#时出现错误,已更正。非常抱歉。
由于此修改,输出示例没有变化。

出力例 3

0
  • 所有空地都在送货路线上,因此您无法创建花园。

入力例 4

4 4
HH.H
H##.
.##.
H..H

出力例 4

-1
  • 从北方 1 从西边来 1 你不能遵守送货规则,因为你不能送货到第格内的房子,或者除非你经过房子,否则你不能送货。

入力例 5

10 10
..##.H....
.H.#......
...#####..
##......#.
.#...#.H..
.....#....
.##H..####
..##....H.
.H..#.....
...#......

出力例 5

36