You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 F 的电脑屏幕可以被划分为 $r$ 行 $c$ 列的网格，第 $i$ 行第 $j$ 列的网格，可以用 $(i,j)$ 来表示。

突然，有一天，小 F 的电脑中了「满屏粉兔」病毒，在电脑屏幕上，出现了 $N$ 只雄粉兔和 $M$ 只雌粉兔。

假设一只粉兔位于 $(i,j)$，若其沿上、下、左、右四个方向中的一个方向行动，可以在不经过「异性粉兔」的情况下离开屏幕范围，那么，这个方向对于该粉兔就是一条「逃跑通道」。

狡兔三窟。我们定义一只粉兔是「合格的粉兔」，当且仅当其至少有三条「逃跑通道」。

例如，如图所示，绿色方格代表雄粉兔，粉色方格代表雌粉兔。位于 $(2,2)$ 的雌粉兔，向上、下、左，都可以不经过雄粉兔的离开屏幕，共有三条「逃跑通道」因此，位于 $(2,2)$ 的粉兔是「合格的粉兔」。而位于 $(4,4)$ 的粉兔，仅有左、右两条「逃跑通道」，因此 $(4,4)$ 的粉兔不是「合格的粉兔」。

现在，给出屏幕上粉兔的分布情况，请问，一共有多少只「合格的粉兔」？

输入格式

输入共 $r+1$ 行。

输入的第一行为四个整数 $r,c,N,M$。

接下来 $r$ 行，每行 $c$ 个字符，第 $i$ 行第 $j$ 个字符 $k_{i,j}$ 描述了网格 $(i,j)$ 的情况：

• 若 $k_{i,j}$ 为 .，则代表 $(i,j)$ 没有粉兔。
• 若 $k_{i,j}$ 为 F，则代表 $(i,j)$ 为雌粉兔。
• 若 $k_{i,j}$ 为 M，则代表 $(i,j)$ 为雄粉兔。

输出格式

输出一行一个整数，代表「合格的粉兔」的只数。

6 5 2 3
.....
.F.M.
.....
.F.F.
...M.
.....

3

提示

• 对于 $30\%$ 的测试数据，$1 \le r,c \le 30$；
• 对于 $100\%$ 的测试数据，$1 \le r,c \le 500$，$0 \le N,M \le r \cdot c$，$k_{i,j}$ 为 .、F、M 中的一个。