Turn On the Light
Time limit1sMemory limit128 MB
Given an N by M grid of diagonal tiles ('/' or '\'), find the minimum number of tile rotations needed to create a diagonal path from top-left to bottom-right corner, using shortest path on a corner graph with 0/1 edge weights.
- Level
Medium6 of 10
- Topics
- Shortest path, Graph, BFS
- Solved
- No attempts yet
Problem
Sunyoung is designing a rectangular electronic circuit with height N and width M. The circuit consists of N × M square tiles, and every tile is parallel to the sides of the rectangle. Each tile has one wire connecting two opposite corners.
The power source is connected to the upper-left corner of the circuit, and the light bulb is connected to the lower-right corner. The bulb turns on only when there is a path along wires from the power source to the bulb. To turn on the bulb, Sunyoung may rotate any number of tiles by 90 degrees.
In the picture above, the bulb is off. If any tile in the second column from the right is rotated by 90 degrees, the power source and the bulb become connected, and the bulb turns on. Find the minimum number of tiles that must be rotated to turn on the bulb.
Input
The first line contains two integers N and M. Each of the next N lines describes the current state of the circuit. Each line has length M, and each character is either / or \.
1 ≤ N, M ≤ 500
Output
If the bulb can be turned on, print the minimum number of tiles that must be rotated. If it is impossible, print NO SOLUTION.