开始: 2026-10-08 00:00:00

【集训06】模拟赛

结束: 2026-10-10 00:00:00
当前  2026-11-04 11:35:03  类型: IOI  状态: 已经结束 

P3. 格子与磁石(magnet)
描述

有一个 H 行 W 列的方格网,部分格子上放着磁石。网格状态由 H 个长度为 W 的字符串 S_1,\dots,S_H 给出:

S_i 的第 j 个字符为 `#` 表示第 i 行第 j 列的格子放了磁石,为 `.` 表示该格为空。

小Z穿着一身**铁甲**,站在某个格子上时,他可以按如下规则移动:

- 若当前格子的**上下左右四个相邻格子中存在磁石**,则他**哪里也去不了**(被磁石吸住,一动都不能动);

- 否则,他可以移动到上下左右相邻的某一个格子(但不能移出网格,也不能走到放有磁石的格子上)。

对每个**没有放磁石**的格子,定义它的**自由度**为:若小Z一开始站在这个格子上,通过反复移动**能够到达的格子个数**(包含起点自己)。

求所有没有放磁石的格子中,自由度的最大值。

> **务必读懂**:「能够到达的格子」指的是**存在某一条移动路线**能到达它,

> **并不要求存在一条路线能一次性把所有这些格子都走遍**。

> 另外,每个空格子自身总是算作「能到达」。


输入

第一行两个整数 H,W(1 \leq H,W \leq 1000),表示网格的行数与列数。

接下来 H 行,第 i 行是一个长度为 W 的、仅由 `.` 与 `#` 组成的字符串 S_i。


输出

输出所有没有放磁石的格子中,自由度的最大值。

样例

输入

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

输出

9

输入

3 3
..#
#..
..#

输出

1
提示

**样例1说明**:把行从上到下、列从左到右编号。站在 (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)。

数据范围:

- 1\le H,W\le 1000;

- H,W 为整数;

- S_i 是仅由 `.` 与 `#` 组成的长度 W 的字符串;

- **至少存在一个**没有放磁石的格子。


提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交