Laser Communication

The cows have installed a new laser‐based communication system in their pasture. The pasture is modeled as a grid of points with dimensions \(W \times H\) (where \(1 \le W \le 100\) and \(1 \le H \le 100\)). Some cells contain obstacles (denoted by *) that block the laser beam while open cells are denoted by .. Two cows (denoted by C) are trying to communicate using a laser. However, the direct line-of-sight may be blocked by obstacles. To overcome this, the cows can install diagonal mirrors that deflect the laser beam by \(90^\circ\).

The task is to determine the minimum number of mirrors that need to be installed so that the laser can travel from one cow to the other. It is guaranteed that a solution exists in the test data.

inputFormat

The first line of input contains two integers W and H, representing the width and height of the grid respectively. The following H lines each contain a string of W characters. Each character is one of the following:

• . representing an open cell
• * representing an obstacle
• C representing a cow (exactly two cows will appear in the grid)

Note that the grid is provided in row order (the first line corresponds to the top row of the grid).

outputFormat

Output a single integer representing the minimum number of mirrors required to enable the laser beam to connect the two cows.

sample

3 3
C.C
...
...

0