USACO 2014 February Contest, Bronze
Problem 1. Mirror Field
Contest has ended.
Log in to allow submissions in analysis mode
Problem 1: Mirror Field [Mark Gordon]
Farmer John has left some old mirrors sitting outside his house, and his
cows, feeling mischievous as always, have stolen them!
The cows have set up the mirrors in a rectangular field measuring N by M
squares (1 <= N, M <= 1,000). In each square, they have placed a double
sided mirror between two of its opposite corners. These two possible
configurations are represented by the '/' character (a mirror connecting
the lower-left corner to the upper-right corner) and the '\' character (a
mirror connecting the upper-left corner to the lower-right corner).
One evening, Bessie the cow brings a laser pointer out to the mirror field.
Standing outside the field, she shines the beam of light either
horizontally or vertically along either a row or column of the field,
causing it to bounce of some number of mirrors. Since the mirrors are all
diagonally oriented, a horizontal beam of light that reflects off a mirror
will end up traveling vertically, and vice versa. Bessie wonders what is
the maximum number of mirrors on which her beam of light can be reflected
at the same time. Given the layout of the mirror field, please help Bessie
compute this number.
PROBLEM NAME: mirror
INPUT FORMAT:
* Line 1: The integers N and M, separated by a space.
* Lines 2..1+N: Each line will contain M '/' or '\' characters,
describing a row of the mirror field.
SAMPLE INPUT (file mirror.in):
3 3
/\\
\\\
/\/
OUTPUT FORMAT:
* Line 1: A single integer indicating the maximum number of times a
horizontal or vertical beam originating outside the mirror
field could be reflected. Please output -1 if it could be
reflected indefinitely.
SAMPLE OUTPUT (file mirror.out):
3
OUTPUT DETAILS:
Bessie can shine the beam downwards above the middle column of her
field to have it reflected 3 times.
Contest has ended. No further submissions allowed.