Tomb Raider

Time limit3sMemory limit512 MB

Summary

Find the fewest gargoyles to rotate so every gargoyle face can see some gargoyle face by light beams in a mirror grid.

Level: Hard9 of 10
Topics: Graph, BFS, Matrix
Solved: No attempts yet

Problem

Hu the Tomb Raider has entered a new tomb! It is full of gargoyles, mirrors, and obstacles. A door guards the treasure, and Hu must unlock it. An ancient inscription on the door gives the secret:

Every face of every gargoyle shall see a face of a gargoyle.

This means the gargoyles must be rotated so that a beam of light can travel from each gargoyle's face to another gargoyle's face, which may be one of its own faces. The beam of light may reflect off mirrors.

The floorplan is an n×m grid of cells:

A Dot (.) is an empty cell.
A Hash (#) is an obstacle.
A Slash (/) is a double-sided mirror, as is a Backslash (\).
A V is a gargoyle with two faces, facing top and bottom.
An H is a gargoyle with two faces, facing left and right.

The tomb is surrounded by walls of mirrors, in addition to the \ and / mirrors. Assume the following about light:

Light travels in a straight line through empty cells.
Two beams of light can cross without interfering with each other.
A \ mirror reflects light coming from the top, bottom, left, or right to the right, left, bottom, or top. A / mirror reflects light coming from the top, bottom, left, or right to the left, right, top, or bottom.
Light is reflected by 180 degrees when it hits a wall, since walls are all mirrors.
Light is blocked by obstacles and gargoyles.

Hu may rotate any gargoyle by 90 degrees. Time is short, so he wants the minimum number of gargoyles that must be rotated to unlock the treasure door.

Input

The first line contains two space-separated integers n and m ( $1 \le n, m \le 500$ ), the dimensions of the tomb. Each of the next n lines contains a string s with $|s| = m$ , describing the floorplan using the characters above.

Output

Output a single integer, the minimum number of gargoyles that must be rotated to unlock the treasure door. If the puzzle has no solution, output $-1$ .

Hint

The image shows Sample Input/Output 1 with the initial configuration on the left and the solution on the right. Three gargoyles are rotated to solve the puzzle.

Examples3

Example 1
Input
```
5 5
/.V.\
./.V.
..#..
.V.#.
\.V./
```
Expected output
```
3
```
Example 2
Input
```
2 5
V...\
H...V
```
Expected output
```
-1
```
Example 3
Input
```
2 2
VV
VV
```
Expected output
```
0
```