Background

Translated from Izborne Pripreme 2019 (Croatian IOI/CEOI Team Selection) D1T2。$\texttt{3s,0.5G}$。

Problem Description

The city government of Zagreb decided to build a new parking lot.

The land is an $N \times M$ rectangle, divided into $N$ rows and $M$ columns, i.e. $N \times M$ cells. We denote the cell in row $i$ and column $j$ by $(i,j)$.

To attract tourists, some cells are pre-determined to contain water scenery. The remaining cells will be converted into parking spaces or lanes. In particular, the entrance/exit of the parking lot is $(1,1)$, and it can only be used as a lane.

Cars can move freely inside the parking lot. Each move can go to one of the four adjacent cells (up, down, left, right), as long as the destination cell is still inside the parking lot.

A valid construction plan must satisfy the following condition:

• For any car parked in a parking space, it must be able to reach the entrance/exit of the parking lot without passing through any other parking space.

Among all valid construction plans, find the maximum possible number of parking spaces.

Input Format

The first line contains two positive integers $N, M$.

Next, an $N \times M$ character matrix describes the land.

• The character in row $i$ and column $j$ is ., meaning it can be used as either a lane or a parking space.
• The character in row $i$ and column $j$ is X, meaning it is used to build water scenery.

Output Format

Output one integer in one line, the maximum number of parking spaces that can be built.

3 3
...
.x.
...

2

3 3
...
..x
...

4

3 6
.x..x.
..x.x.
......

3

4 5
....x
....x
..x..
.x..x

7

Hint

Explanation for sample $4$: let P denote a parking space, as follows.

.PPPx
....x
.Px.P
PxP.x

For $100\%$ of the data, it is guaranteed that:

• $1 \le N \le 6$；
• $1 \le M \le 100$；
• No water scenery will be built at $(1,1)$。

Constraints:

Translated by ChatGPT 5