j06618. 冲刺·粘胶迷宫 · 林老师的题库

题目描述

清扫机器人小扫在一座 $H$ 行 $W$ 列的迷宫里做性能测试。迷宫中散落着一些粘胶桩（#），其余是空地（.）。

小扫可以站在任意一个空格上开始测试。测试中它每次移动到相邻四格之一的空格；但注意——如果它当前所在格的上下左右四格中存在粘胶桩，它就会被牢牢粘住，无法再移动（被粘住之前走过的格子都算已覆盖，包括它被粘住的那格）。

定义一个出发点的「自由度」为：从这个格子开始测试，能够覆盖的格子总数。请你求出所有空格中自由度的最大值。

第一行两个整数 $H$ 和 $W$ 。

接下来 $H$ 行，每行一个长度为 $W$ 的、由 # 和 . 组成的字符串。

一行一个整数，表示最大自由度。

输入

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

输出

从第 $2$ 行第 $3$ 列出发，可以走到 (2,4)(1,4)(1,5)(2,5)(3,4)(2,2)(1,3)(3,3)，加上出发点共 $9$ 格——其中 (2,2) 走进去就会被粘住，只能作为终点。

对于 $100%$ 的数据， $1 \leq H, W \leq 1000$ ，且网格中至少有一个空格。