1302 . Switch the Lamp On
Description
Casper is designing an electronic circuit on a N * M rectangular grid plate. There are N * M square
tiles that are aligned to the grid on the plate. Two (out of four) opposite corners of each tile are
connected by a wire.
A power source is connected to the top left corner of the plate. A lamp is connected to the bottom
right corner of the plate. The lamp is on only if there is a path of wires connecting power source to
lamp. In order to switch the lamp on, any number of tiles can be turned by 90 degrees (in both directions).
In the picture above the lamp is off. If any one of the tiles in the second column from the right is
turned by 90 degrees, power source and lamp get connected, and the lamp is on.
Write a program to find out the minimal number of tiles that have to be turned by 90 degrees to switch the
lamp on.
Input Format
The first line of input contains two integer numbers N and M, the dimensions of the plate. In each of
the following N lines there are M symbols -- either \ or / -- which indicate the direction of the wire
connecting the opposite vertices of the corresponding tile.
1 ≦ N, M ≦ 500
Output Format
There must be exactly one line of output. If it is possible to switch the lamp on, this line must contain
only one integer number: the minimal number of tiles that have to be turned to switch on the lamp.
If it is not possible, output the string: NO SOLUTION
Sample Input 1
3 5 \\/\\ \\/// /\\\\
Sample Output 1
1
Hints
The example input corresponds to the picture.
Problem Source
Migrated from old NTUJ.
BOI2011 Competition Day 1
Subtasks
| No. | Testdata Range | Score |
|---|