这个页面待填充。

[ABC351D] Grid and Magnet

题面翻译

有一个用字符类型表示的 $H$ 行 $W$ 列的地图 $S$，如果 $S_{i,j}$ 是字符 . 则代表这一格是空地，如果是 # 则代表这一格上有一个磁铁。现有一个小人从一个格子上出发，每次可以到达与之相邻（上、下、左、右）的四个格子，但如果有一个磁铁与之相邻（上下左右的四个格子中至少有一个磁铁）他就不能动了。求小人从某一格出发，经过任意多次运动，可以到达的格子的最大数量。

输入格式

入力は以下の形式で標準入力から与えられる。

$ H $ $ W $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_H $

输出格式

マス目のうち磁石が置かれていないマスの中における、マスの自由度の最大値を出力せよ。

样例输入 #1

1
2
3
4
3 5
.#...
.....
.#..#

样例输出 #1

1
9

样例输入 #2

1
2
3
4
3 3
..#
#..
..#

样例输出 #2

1
1

制約

  • $ 1\leq\ H,W\leq\ 1000 $
  • $ H,W $ は整数
  • $ S_i $ は . と # のみからなる長さ $ W $ の文字列
  • 磁石の置かれていないマスが少なくとも $ 1 $ つ存在する。

Sample Explanation 1

上から $ i $ 行目かつ左から $ j $ 列目のマスを $ (i,j) $ で表します。 高橋君が最初に $ (2,3) $ にいるとき、高橋君の移動の例としては次のようなものなどが考えられます。 - $ (2,3)\to\ (2,4)\to\ (1,4)\to\ (1,5)\to\ (2,5) $ - $ (2,3)\to\ (2,4)\to\ (3,4) $ - $ (2,3)\to\ (2,2) $ - $ (2,3)\to\ (1,3) $ - $ (2,3)\to\ (3,3) $ よって、途中で到達しているマスも含めて高橋君は $ (2,3) $ から少なくとも $ 9 $ 個のマスに到達することができます。 一方、これら以外のマスには到達することができないため、$ (2,3) $ の自由度は $ 9 $ となります。 これは磁石が置かれていない各マスの自由度のうち最大であるため、$ 9 $ を出力します。

Sample Explanation 2

磁石が置かれていないどのマスについても、上下左右に隣り合うマスのいずれかに磁石が置かれています。 よって、磁石が置かれていないどのマスからも移動することはできず、マスの自由度は $ 1 $ となります。 そのため、$ 1 $ を出力します。