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

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

题目描述

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

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

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

输入格式

第一行:宽度和高度 HHWW1H,W40001 \le H, W \le 4000

下面一个 H×WH \times W 的矩阵

输出格式

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

样例

样例输入

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

样例输出

2

样例解释

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

数据范围与提示

对于 30%30\% 的测试数据,N200,H,W500N \le 200, H, W \le 500。 对于所有数据,1H,W40001 \le H, W \le 4000

翻译来自 abcdabcd987。