[GESP202503 四级] 荒地开垦

普及- GESP 四级 真题

题目描述

小杨有一大片荒地,可以表示为一个 $n$ 行 $m$ 列的网格图。

小杨想要开垦这块荒地,但荒地中一些位置存在杂物,对于一块不存在杂物的荒地,该荒地可以开垦当且仅当其上下左右四个方向相邻的格子均不存在杂物。

小杨可以选择至多一个位置,清除该位置的杂物,移除杂物后该位置变为荒地。小杨想知道在清除至多一个位置的杂物的情况下,最多能够开垦多少块荒地。

输入格式

第一行包含两个正整数 $n, m$,含义如题面所示。

之后 $n$ 行,每行包含一个长度为 $m$ 且仅包含字符 .# 的字符串。如果为 .,代表该位置为荒地;如果为 #,代表该位置为杂物。

输出格式

输出一个整数,代表在清除至多一个位置的杂物的情况下,最多能够开垦的荒地块数。

数据范围

样例解释

移除第二行从左数第二块空地的杂物后:

.....
....#
.....

第一行从左数前 $4$ 块荒地,第二行从左数前 $3$ 块荒地,第三行从左数前 $4$ 块荒地,均可开垦,$4+3+4=11$。

数据范围

对于全部数据,有 $1\leq n,m\leq 1000$。

样例输入 1

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

样例输出 1

11
时间限制: 1000ms
内存限制: 256MB
通过率: 0.0%
提交数: 0

设置

导航栏小工具

时钟
显示实时时钟(默认组件)
📝
代码粘贴板
快速创建和分享代码片段