返回首页 返回题库

荒地开垦

C++ 简单 GESP四级真题 #枚举#二维网格

题目描述

题面描述

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

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

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

输入格式

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

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

输出格式

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

样例1

输入:

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

输出:

11

样例解释

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

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

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

数据范围

对于全部数据,保证有。

时间/内存限制

时间限制:1.0 s

内存限制:512.0 MB

💡 查看提示(先自己想一想再看)
考察二维网格的遍历与统计能力。首先统计不需要清除任何杂物时就能开垦的荒地数量,再统计如果清除某个杂物位置能够额外新增的可开垦荒地数量,取最大值加到初始数量上即可得到答案。注意边界位置的处理,避免数组越界。
⚙ 开始做这道题 0 人做过 · 0 收藏 · 12 浏览

讨论(0)