题号：NC221260
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Hu the Tomb Raider has entered a new tomb! It is full of gargoyles, mirrors, and obstacles. There
is a door, with treasure beyond. Hu must unlock the door guarding the treasure. On that door is
is a door, with treasure beyond. Hu must unlock the door guarding the treasure. On that door is
written, in an ancient tongue, the secret to opening the door:
Every face of every gargoyle shall see a face of a gargoyle.
This means that the gargoyles must be rotated in such a way that there is a path for a beam of light
to connect each gargoyle’s face to another gargoyle’s face (possibly of its own). The beam of light
may reflect in mirrors.
to connect each gargoyle’s face to another gargoyle’s face (possibly of its own). The beam of light
may reflect in mirrors.
The floorplan of the tomb can be described as a rectangular n×m grid of cells:
A Dot (‘.’) represents an empty cell.
A Hash (‘#’) represents an obstacle.
A Slash (‘/’) represents a double-sided mirror, as does a Backslash (‘\’) .
A character ‘V’ represents a gargoyle with two faces facing top and bottom.
A character ‘H’ represents a gargoyle with two faces facing left and right.
A Hash (‘#’) represents an obstacle.
A Slash (‘/’) represents a double-sided mirror, as does a Backslash (‘\’) .
A character ‘V’ represents a gargoyle with two faces facing top and bottom.
A character ‘H’ represents a gargoyle with two faces facing left and right.
In addition to the ‘\’ and ‘/’ mirrors, the tomb is surrounded by walls of mirrors. The following
common sense about light is assumed:
common sense about light is assumed:
1. Light travels in a straight line through empty cells.
2. Two beams of light can intersect without interfering with each other.
3. A ‘\’ mirror reflects light coming from the top/bottom/left/right to the right/left/bottom/top.
A ‘/’ mirror reflects light coming from the top/bottom/left/right to the left/right/top/bottom.
4. Light is reflected by 180 degrees when it hits a wall (walls are all mirrors).
5. Light is blocked by obstacles and gargoyles
2. Two beams of light can intersect without interfering with each other.
3. A ‘\’ mirror reflects light coming from the top/bottom/left/right to the right/left/bottom/top.
A ‘/’ mirror reflects light coming from the top/bottom/left/right to the left/right/top/bottom.
4. Light is reflected by 180 degrees when it hits a wall (walls are all mirrors).
5. Light is blocked by obstacles and gargoyles
Hu may rotate any gargoyle by 90 degrees. As time is running short, he wants to know the
mini-mum number of gargoyles that have to be rotated in order to unlock the treasure door.
输入描述:
The first line of input contains two space-separated integers n and m (1 ≤ n,m ≤ 500), which are
the dimensions of the tomb.
Each of the next n lines contains a string s (|s| = m) with the characters described above. This is
the floorplan of the tomb.
输出描述:
Output a single integer, which is the minimum number of gargoyles that have to be rotated in order
to unlock the treasure door. If the puzzle has no solution, output −1.
备注:
The above are illustrations of Sample Input/Output 1 with the initial configuration on the left, andthe solution of the puzzle on the right. Three gargoyles are rotated to solve the puzzle.
