P7208 [COCI 2019/2020 #1] Zoo

On Christmas night in $2010$, Zagreb was covered in snow. Zdravko decided to leave his castle and take a walk in Maksimir Park. Unfortunately, this wonderful winter night was disturbed by a devil. Zdravko scared it away, but the shout caused chaos in the zoo. Even worse, a group of tigers and bulls were forced to try to escape and find a quiet place to sleep.

During the escape, the animals need to pass through a rectangular area of size $R \times C$. They must enter this area from the upper-left corner and leave from the lower-right corner. To leave faster, the animals pass through one after another, and each one walks in a random path in four directions (up, down, left, right). That is, an animal does not have to choose the shortest path, and it may stay on the same cell multiple times (including the upper-left and lower-right corners). Each time an animal steps onto a cell, it leaves a footprint. If the current cell already has a footprint, then the animal erases the existing footprint and leaves its own footprint. Your task is, based on the footprints left in the snow, to find the minimum possible number of animals that could have escaped.

The first line contains the two integers $R, C$ mentioned above. The next $R$ lines each contain $C$ characters describing the rectangular area. The character `T` means a tiger footprint, `B` means a bull footprint, and `*` means untouched snow with no trace of walking. You may assume that at least $1$ animal passed through the rectangular area, and every animal that enters the area eventually leaves it.

Output the minimum possible number of escaping animals.

#### Sample Explanation Below is a picture explanation for the second sample:  #### Constraints | Subtask | Points | Constraints | | :----------: | :----------: | :----------: | | $1$ | $45$ | $2 \le R, C \le 100$ | | $2$ | $65$ | $2 \le R, C \le 1000$ | #### Notes **The scoring of this problem follows the original COCI problem setting, with a full score of $110$.** **Translated from [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #1](https://hsin.hr/coci/archive/2019_2020/contest1_tasks.pdf) _T5 Zoo_.** Translated by ChatGPT 5