[BalticOI2013] Tracks in the Snow
题目描述
有一个含 $H$ 行，$W$ 列的字符矩阵，初始全为 `.`。
有两种动物，狐狸和兔子，将会从左上角走到右下角，狐狸会留下 `F` 的痕迹，兔子会留下 `R` 的痕迹。
痕迹会相互覆盖。
走路规则如下：
- 可以往返走；
- 不可以走对角线；
- 不可以跳格子；
- 不可能有两只动物一起走。
现在您得到了这个被动物们走过的矩阵，请求出至少有几个动物走过了该矩阵。
输入输出格式
输入格式
第一行为两个整数 $H,W$。
接下来 $H$ 行，一行 $W$ 个字符，表示整个字符矩阵。
输出格式
仅一行一个整数，表示至少有几个动物走过了该矩阵。
输入输出样例
输入样例 #1
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF输出样例 #1
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](https://boi.cses.fi/tasks.php) [Day 2](https://boi.cses.fi/files/boi2013_day2.pdf) T2 Tracks in the Snow。