Problem Description

There is a character matrix with $H$ rows and $W$ columns, initially all ..

There are two kinds of animals, foxes and rabbits, which will walk from the top-left corner to the bottom-right corner. A fox leaves F tracks, and a rabbit leaves R tracks.

Tracks can overwrite each other.

The walking rules are as follows:

• They can move back and forth.
• They cannot move diagonally.
• They cannot jump over cells.
• It is impossible for two animals to walk at the same time.

Now you are given the matrix after the animals have walked through it. Please find the minimum number of animals that could have walked through this matrix.

Input Format

The first line contains two integers $H, W$.

Then follow $H$ lines, each with $W$ characters, describing the whole character matrix.

Output Format

Output one integer in a single line, indicating the minimum number of animals that could have walked through this matrix.

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

2

Hint

Constraints and Limits

• For the testdata worth $30$ points, it is guaranteed that the answer $\le 200$, and $H, W \le 500$.
• For $100\%$ of the testdata, it is guaranteed that $1 \le H, W \le 4 \times 10^3$, the answer $\ge 1$, and the input characters are only ., R, or F.

Notes

This problem is translated from Baltic Olympiad in Informatics 2013 Day 2 T2 Tracks in the Snow.

Translated by ChatGPT 5