Problem Background

On Christmas Eve in 2010, Zagreb was a world of snow.

Zdravko decided to leave his castle and take a walk in Maksimir Park. Unfortunately, a wonderful winter night was disturbed by a devil. Zdravko scared it away, but this scare caused a commotion in the zoo. More seriously, a group of tigers and bulls were driven to escape and find a quiet place to sleep.

Problem Description

During their escape, the animals need to pass through a rectangular area of size $R \times C$. They must enter from the top-left corner and exit from the bottom-right corner.

To leave faster, the animals will pass one after another, moving in random directions (up, down, left, right). This means that each animal does not necessarily choose the shortest path and may stay in the same position multiple times (including the top-left and bottom-right corners).

Each time an animal steps on a square, it leaves a footprint. If there is already a footprint at the current position, the animal will erase the current footprint and leave its own.

Your task is to determine the minimum possible number of escaping animals based on the footprints in the snow.

Input Format

The first line contains two integers $R$ and $C$ as mentioned in the problem.

The next $R$ lines, each containing $C$ characters, represent the rectangular area. The character T represents a tiger's footprint, B represents a bull's footprint, and * represents untouched snow.

You can assume that at least one animal has passed through the rectangular area, and every animal that enters the area eventually leaves it.

Output Format

Output the minimum possible number of escaping animals.

Sample Input and Output

Sample Input #1

4 4
TT*T
*TTT
***T
***T

Sample Output #1

1

Sample Input #2

3 5
TTBB*
*T*B*
*TTTT

Sample Output #2

2

Sample Input #3

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

Sample Output #3

3

Notes

Sample Explanation

The following is an image explanation for the second sample:

Data Range and Constraints

Notes

This problem's score is set according to the original COCI contest, with a full score of $110$.

The problem is translated from COCI2019-2020 CONTEST #1 T5 Zoo.

见题面 Input 部分

见题面 Output 部分