P7208 [COCI 2019/2020 #1] Zoo
题目背景
$2010$ 年圣诞节的晚上，萨格勒布是一片雪的世界。
Zdravko 决定离开自己的城堡，并在 Maksimir 公园散步。不幸的是，一个美妙的冬夜竟被一个魔鬼所侵扰。Zdravko 将其吓走，但这声惊吓引起了动物园的骚动。更严重的是，一群老虎和公牛被逼的想要逃跑，并找一个安静的地方睡觉。
题目描述
在逃跑的过程中，动物们需要通过一个 $R \times C$ 的矩形区域。它们必须从这片区域的左上角进入，并从右下角离开。
为了更快地离开这里，动物们将一个接着一个地经过，并以一种随机的路径往四个方向（上、下、左、右）行走。也就是说，每一个动物并不一定选择最短路径，而且可能在同一位置停留数次（包括左上角和右下角）。
动物们每踏上一个格子，便会留下脚印。如果当前位置已经有了脚印，那么该动物会擦除当前的脚印，并留下自己的脚印。
你的任务是根据雪地脚印的情况，求出逃跑动物可能的最少数量。
输入格式
第一行包含题中所提到的两个整数 $R,C$。
接下来的 $R$ 行，每行有 $C$ 个字符，表示矩形的区域。其中，字符 `T` 表示老虎的脚印， `B` 表示公牛的脚印，`*` 表示没有行走痕迹的雪地。
你可以认为，至少有 $1$ 个动物经过了矩形区域，并且每个进入矩形区域的动物都最终离开了区域。
输出格式
输出逃跑动物可能的最少数量。
说明/提示
#### 样例解释
下列是对第二个样例的图片解释：
#### 数据范围及约定
| Subtask | 分值 | 数据范围及约定 |
| :----------: | :----------: | :----------: |
| $1$ | $45$ | $2 \le R, C \le 100$ |
| $2$ | $65$ | $2 \le R, C \le 1000$ |
#### 说明
**本题分值按 COCI 原题设置，满分 $110$。**
**题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #1](https://hsin.hr/coci/archive/2019_2020/contest1_tasks.pdf) _T5 Zoo_ 。**