AT_abc351_d [ABC351D] Grid and Magnet

题目描述

有一个 $H$ 行 $W$ 列的格子，其中有若干个（也可能为 $0$ 个）格子上放置了磁铁。
格子的状态由 $H$ 个长度为 $W$ 的字符串 $S_1,S_2,\ldots,S_H$ 表示，$S_i$ 的第 $j$ 个字符为 # 时，表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子上放置了磁铁，为 . 时表示该格子上没有放置任何东西。

高桥君穿着铁制盔甲，在某个格子时可以按如下方式移动：

• 如果当前格子的上下左右相邻的任意一个格子上放置了磁铁，则无法移动到任何地方。
• 否则，可以选择上下左右相邻的任意一个格子并移动到该格子。
  但不能移动到格子外面。

对于没有放置磁铁的每个格子，定义该格子的自由度为“最初高桥君在该格子时，从该格子出发通过多次移动能够到达的格子的数量”。
请你求出所有没有放置磁铁的格子中，自由度的最大值。

需要注意的是，在自由度的定义中，“能够通过多次移动到达的格子”指的是，从最初所在的格子出发，通过若干次（也可以为 $0$ 次）移动能够到达的格子，不要求存在一种移动方式能够遍历所有这些格子。特别地，每个没有放置磁铁的格子本身总是包含在“能够到达的格子”之中。

输入格式

输入按以下格式从标准输入读入。

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

输出格式

请输出所有没有放置磁铁的格子中，自由度的最大值。

输入输出样例 #1

输入 #1

3 5
.#...
.....
.#..#

输出 #1

9

输入输出样例 #2

输入 #2

3 3
..#
#..
..#

输出 #2

1

说明/提示

限制条件

• $1 \leq H, W \leq 1000$
• $H, W$ 为整数
• $S_i$ 是仅由 . 和 # 组成的长度为 $W$ 的字符串
• 至少存在一个没有放置磁铁的格子

样例解释 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$。

样例解释 2

对于没有放置磁铁的任意格子，其上下左右相邻的格子中至少有一个放置了磁铁。
因此，从没有放置磁铁的任意格子都无法移动，自由度为 $1$。
所以输出 $1$。

由 ChatGPT 4.1 翻译