DMOPC '21 Contest 10 P3 - Peculiar Reflections

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

Rudeus recently discovered a rather peculiar device. The device is an N \times M grid of tiles, each one containing a diagonal mirror, represented as either / or \. The device also comes with a small laser source, shining in from above the top-left corner and a target positioned just below the bottom-right corner.

When the laser hits a mirror, it bounces perfectly off the center of the mirror, reflecting at a 90 degree angle depending on the direction of the mirror. Mirrors can also be flipped, which changes a \ mirror to a / mirror and vice versa.

It seems as though the goal when using this device is to have the laser shine onto the target. To accomplish this, you can flip the directions of some mirrors.

Rudeus wonders: what is the minimum number of mirrors that he needs to flip to get the laser to shine onto the target?

Constraints

1 \le N \times M \le 10^6

Each character in the grid is either / or \.

Subtask 1 [30%]

Each character in the grid is \.

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains N and M.

The next N lines each contain M characters, representing the grid.

Output Specification

Output the minimum number of mirror flips required to have the laser hit the target. If it is impossible, output -1.

Sample Input 1

4 5
\/\/\
/\///
//\//
/////

Sample Output 1

5

Explanation for Sample 1

The original grid is shown below:

And here is a sequence of valid flips with the laser's path traced over. Flipped mirrors are highlighted in black.

Sample Input 2

1 1
\

Sample Output 2

-1

Explanation for Sample 2

Note that the lightbulb is below the bottom-right cell.


Comments

There are no comments at the moment.