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

题目描述

在一片长方形的草地上，有 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

解释：最少需要 2 只动物，第一只是兔子（留下 R），第二只是狐狸（留下 F，覆盖了部分 R）。

数据范围与提示

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

对于所有数据，$1 \le H, W \le 4000$。