[AdditionalFile2686.zip](file://AdditionalFile2686.zip?type=additional_file)

#2686. 「BalticOI 2013」雪地足迹 Tracks in the Snow

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

在一片长方形的草地上，有 $2$ 种动物——兔子和狐狸活动。兔子走过草地会留下 R，狐狸走过草地会留下 F。每只动物从左上角进入草地，从右下角走出草地。其间，它可以上下左右乱跳（可以重复），经过的格子会被覆盖上它的脚印。每次草地上最多只有一只动物。

........      RRR.....      FFR.....
........      ..RRR...      .FRRR...
........      ..R.....      .FFFFF..
........      ..RRRR.R      ..RRRFFR
........      .....RRR      .....FFF

给你地图，问最少有多少只动物走过了草地。

输入格式

第一行：宽度和高度 $H$ 和 $W$（$1 \le H, W \le 4000$）

下面一个 $H \times W$ 的矩阵

输出格式

至少有多少只动物走过了草地。

样例

输入

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

输出

2

........ RRR..... FFR.....
........ ..RRR... .FRRR...
........ ..R..... .FFFFF..
........ ..RRRR.R ..RRRFFR
........ .....RRR .....FFF

数据范围与提示

对于 $30\%$ 的测试数据，$N \le 200, H, W \le 500$。 对于所有数据，$1 \le H, W \le 4000$。

翻译来自 abcdabcd987。