B4263 [GESP202503 Level 4] Reclaiming Wasteland

Problem Background

Corresponding multiple-choice / true-false questions: https://ti.luogu.com.cn/problemset/1176

Problem Description

Xiao Yang has a large piece of wasteland, which can be represented as a grid with $n$ rows and $m$ columns.

Xiao Yang wants to reclaim this wasteland. Some positions in the wasteland contain debris. A debris-free plot of wasteland can be reclaimed if and only if none of its four adjacent plots (up, down, left, right) contains debris.

Xiao Yang may choose at most one position and clear the debris there; once removed, that position becomes wasteland. Xiao Yang wants to know the maximum number of wasteland plots he can reclaim after clearing debris at at most one position.

Input Format

The first line contains two positive integers $n, m$, as described.

The following $n$ lines each contain a string of length $m$ consisting only of the characters . and #. A . means the position is wasteland; a # means the position has debris.

Output Format

Output one integer: the maximum number of wasteland plots that can be reclaimed after clearing debris at at most one position.

Sample Input

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

Sample Output

11

Sample Explanation

After clearing the debris in the second plot from the left in the second row:

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

The first row has $4$ reclaimable wasteland plots from the left; the second row has $3$; the third row has $4$. All can be reclaimed, and $4 + 3 + 4 = 11$.

Constraints

For all data, $1 \le n, m \le 1000$ is guaranteed.