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$ 的矩阵

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

........ 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。