시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 (추가 시간 없음) | 512 MB | 38 | 17 | 15 | 45.455% |
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 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.
The floorplan of the tomb can be described as a rectangular n×m grid of cells:
In addition to the ‘\’ and ‘/’ mirrors, the tomb is surrounded by walls of mirrors. The following common sense about light is assumed:
Hu may rotate any gargoyle by 90 degrees. As time is running short, he wants to know the minimum 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.
5 5 /.V.\ ./.V. ..#.. .V.#. \.V./
3
2 5 V...\ H...V
-1
2 2 VV VV
0
The above are illustrations of Sample Input/Output 1 with the initial configuration on the left, and the solution of the puzzle on the right. Three gargoyles are rotated to solve the puzzle.