← 返回题目列表

AtCoder · typical90_bt

072. 环线铁路规划(★4)

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

配点: 4 点

問題文

ABC 王国用 H 行 W 列的格子表示。每个格子是山的格子和 按字典顺序比较平原的格子之一。从上面算起, i 第几行,从左边开始 j 列的格子是山的格子,则为 c_{i,j} 是 您也可以写 # ,是平原的格子,则为 c_{i,j} 是 您也可以写 . 。

你想建铁路线路。铁路线路的路径必须满足以下所有条件。

条件1 从某个格子作为起点,移动到共享边的相邻格子 k 回 (3 \le k) 重复进行,形成以起点结束的路径。
条件2 k 对于每次移动,移动到的格子必须不同。(起点和终点可以相同)
条件3 不经过山的格子。

例如从左边 1 号铁路线路符合条件,但从左起 2, 3, 4, 5 号铁路线路不符合条件。

请找出铁路线路经过的格子数可能的最大值。但是,如果不存在符合条件的铁路线路,请报告这一情况。

制約

  • H, W 是正整数
  • H \times W \leq 16
  • c_{i,j} 是 您也可以写 # 或 至少 .
  • c_{i,j} 是 在 . 是 i,j (1 \leq i \leq H,1 \leq j \leq W) 是 在 1 存在一个以上

入力

输入是按以下格式从标准输入给出的。

H W
c_{1,1} c_{1,2} \cdots c_{1,W}
c_{2,1} c_{2,2} \cdots c_{2,W}
\vdots
c_{H,1} c_{H,2} \cdots c_{H,W}

出力

请输出铁路线路经过的格子数的最大值。

如果不存在符合条件的铁路线路,请改为输出 -1 请输出。


入力例 1

3 3
...
.#.
...

出力例 1

8

例如,以下铁路线路经过 8 个格子。


入力例 2

1 6
......

出力例 2

-1

由于不存在符合条件的铁路线路,-1 可以输出这个。


入力例 3

4 4
....
#...
....
...#

出力例 3

12

例如,以下铁路线路经过 12 个格子。