#P51241. 「COCI 2019.10」Zoo

「COCI 2019.10」Zoo

题目描述

译自 COCI 2019/2020 Contest #1 T5「Zoo

一个圣诞节的晚上,一个人离开了他的家,到对面的公园去散步。

不幸的是,一个怪物的出现打破了夜晚的宁静。这个怪物突然出现在这个人的面前,但这个人用一声咆哮,将这个怪物吓跑了。

这个人不知道,他的咆哮打扰到了附近动物园的动物们。动物园里的老虎和牛非常恼火,它们决定逃离动物园,找到一个安静的地方度过剩下的夜晚。

在逃跑的时候,动物们需要穿越一个 R×CR \times C 的矩形区域。所有动物需要从左上角的方格进入该区域,从右下角的方格离开该区域。为了不引起注意,所有动物将一个接一个通过该区域。动物们每步可以向上下左右四个方向移动,但它们不一定沿着最短的路径行进,同一个动物也可能多次经过同一个方格。由于地面被雪覆盖,动物经过时会留下脚印。如果一个方格里已经留下了足迹,另外一个动物通过这个方格时,会擦除原来留下的足迹,留下新的足迹。

您现在需要根据整个矩形区域内留下足迹的情况,算出至少有多少只动物逃离了动物园。

输入格式

第一行两个整数 R,CR,C

接下来 RR 行,每行 CC 个字符,描述题目中所述的矩形区域。T 代表该格留下了老虎的足迹,B 代表该格留下了牛的足迹,* 代表该格没有留下任何足迹。

输出格式

输出逃离动物园的动物数量的最小值

样例 1

4 4
TT*T
*TTT
***T
***T
1
3 5
TTBB*
*T*B*
*TTTT
2

img.jpg

7 5
BT***
BTBBB
BTTTB
BBT*B
BBT*B
BBT**
*BBBB
3

数据范围与提示

子任务 1(40 分):2R,C1002 \leq R,C \leq 100
子任务 2(60 分):2R,C10002 \leq R,C \leq 1000