Baltic OI '13 P5 - Tracks in the Snow

View as PDF
Submit solution
Points: 12 (partial)
Time limit: 2.0s
Memory limit: 1G
Problem types
Baltic Olympiad in Informatics: 2013 Day 2, Problem 2

There is a rectangular meadow in a forest, having been covered with a blanket of fresh snow in the morning (left in the figure below).

Rabbits and foxes, who live in the forest, are crossing the meadow and leave their tracks in the snow. They always enter in the upper left corner and leave the meadow from the lower right corner. In between they can move back and forth, playing in the snow, even crossing their own tracks. At any time there is at most one animal on the meadow. No animal enters the meadow more than once. The movements of the animals can be described by dividing the meadow into quadratic cells. The animals never move diagonally in a single step and they never jump over a cell. When an animal enters a cell its tracks will cover all previous tracks left in this cell.

For example, first a rabbit crossed the meadow from top-left to bottom-right (middle in the figure). After that, a fox crossed, and now his tracks are partially covering the rabbit's (right in the figure).

........    RRR.....    FFR.....
........    ..RRR...    .FRRR...
........    ..R.....    .FFFFF..
........    ..RRRR.R    ..RRRFFR
........    .....RRR    .....FFF

You are given a map of the meadow at some time after indicating for each cell if there are any visible tracks and whether they were left by a rabbit or by a fox (right in the figure). You are interested in the local wildlife population. Write a program to determine the minimal possible number N of animals that must have crossed the meadow to leave the given pattern of tracks in the snow.

Input

The first line contains two integers H and W, the height and the width of the map of the meadow. H lines follow with exactly W characters on each: the map, where . marks untouched snow, R a spot where a rabbit's track is the topmost one, and F a spot where a fox's track is the topmost one. There is at least one track on the meadow.

Output

The output should consist of a single integer: the minimal number N \ge 1 of animals that could have left the tracks given in the input.

Constraints

1 \le H, W \le 4\,000

In test cases worth 30 points: N \le 200 and H, W \le 500

Sample Input

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

Sample Output

2

Comments