题目背景

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

题目描述

萨格勒布市政府决定修建一个新停车场。

土地是 $N\times M$ 的矩形，被划分为 $N$ 行 $M$ 列 $N\times M$ 个格子。我们记第 $i$ 行第 $j$ 列的格子为 $(i,j)$。

为了吸引游客，事先确定了一些格子内建设水景。剩下的格子将被改造成停车位或车道。特别地，停车场的出入口为 $(1,1)$，只能用作车道。

车辆可以在停车场内自由移动，每次可以移动到上下左右四个相邻的格子（只要移动到的格子仍然属于停车场内）。

一个合法的修建方案必须满足以下条件：

• 任意一辆停在停车位内的车，都能在不经过其他停车位的情况下，到达停车场的出入口。

求出所有合法修建方案中，修建停车场数量的最大值。

输入格式

第一行，两个正整数 $N,M$。

接下来，一个 $N\times M$ 的字符矩阵描述土地。

• 第 $i$ 行第 $j$ 列的字符为 .，代表这里可以被用作车道或者停车位；
• 第 $i$ 行第 $j$ 列的字符为 X，代表这里被用来建设水景。

输出格式

输出一行一个整数，即能够修建停车位数量的最大值。

3 3
...
.x.
...

2

3 3
...
..x
...

4

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

3

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

7

提示

样例 $4$ 解释：记 P 为停车位，如下所示。

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

对于 $100\%$ 的数据，保证：

• $1\le N\le 6$；
• $1\le M\le 100$；
• 不会在 $(1,1)$ 上修建水景。

子任务编号	$N\le$	$M\le$	得分
$1$	$4$	$4$	$10$
$2$		$100$	$10$
$3$	$3$		$20$
$4$	$4$	$100$
$5$	$5$	$100$
	$6$