#3137. [Baltic2013]tracks

[Baltic2013]tracks

题目描述

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

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

输入格式

第一行:宽度和高度 hhww,下面一个 h×w h \times w 的矩阵。

输出格式

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

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

数据规模与约定

对于 100%100\% 的数据,1h,w4×1031 \le h,w \le 4 \times 10^3

题目来源

abcdabcd987提供。