题目描述

有一个含 $H$ 行，$W$ 列的字符矩阵，初始全为 .。

有两种动物，狐狸和兔子，将会从左上角走到右下角，狐狸会留下 F 的痕迹，兔子会留下 R 的痕迹。

痕迹会相互覆盖。

走路规则如下：

• 可以往返走；
• 不可以走对角线；
• 不可以跳格子；
• 不可能有两只动物一起走。

现在您得到了这个被动物们走过的矩阵，请求出至少有几个动物走过了该矩阵。

输入格式

第一行为两个整数 $H,W$。

接下来 $H$ 行，一行 $W$ 个字符，表示整个字符矩阵。

输出格式

仅一行一个整数，表示至少有几个动物走过了该矩阵。

5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF

2

提示

数据范围及限制

• 对于 $30$ 分的数据，保证答案 $\le 200$，$H,W\le 500$。
• 对于 $100\%$ 的数据，保证 $1\le H,W\le 4\times 10^3$，答案 $\ge 1$，读入的字符只会是 . 或 R 或 F。

说明

本题译自 Baltic Olympiad in Informatics 2013 Day 2 T2 Tracks in the Snow。