← 返回题单
题单练习 广度优先搜索
← 上一题 下一题 →

A5405 | Grid and Magnet

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

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

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

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

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

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

输入格式

第一行输入两个正整数$H$，$W$
接下来$H$行，每行输入一个长度为$W$的字符串

输出格式

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

输入输出样例

输入 #1
3 5
.#...
.....
.#..#
输出 #1
9
输入 #2
3 3
..#
#..
..#
输出 #2
1
C++ 编辑器
输入
输出