24735: 【USACO2013JAN】镜子{Bronze题1}

[提交][状态][讨论版][命题人:]

题目描述

1.镜子{Bronze1}

【问题描述】

【文件输入】

【文件输出】

输出共一行，一个整数，表示调整的镜子的编号。若无需调整则输出0，若调整后仍不能看到则输出-1。

【输入样例】

5 6 2

3 0 /

0 2 /

1 2 /

3 2 \

1 3 \

【输出样例】

4

【样例说明】

提示

Analysis: Mirrors by Jonathan Paulson

N is quite small; even an O(N^3) algorithm
is fast enough.

We can actually just simulate（模拟） the problem. Check if the current
configuration（配置）
of mirrors is OK. If not, check flipping（翻转） each mirror one by one (in order!). If
none of those work, then it is impossible.

To check if a given configuration is OK, we can just
simulate it. Keep track（记录）of the current position and direction; then find the next
mirror in that direction; change direction according to bouncing off the
mirror; repeat. If you get to the barn, the configuration is good. If you run
off the edge (i.e. no mirror in that direction), the configuration is bad. If
you get trapped in a cycle (this is a tricky case!), the configuration is bad.
Since you will hit each mirror at most twice (or else you are in a cycle!),
this is O(n*(time to find next mirror)). So even a simple O(n) scan to find the
next mirror is fast enough.

So this gives us an O(N^3) solution, which is fast
enough. The Java solution below uses an O(log n) algorithm to find the next
mirror (by storing a sorted
list of the mirrors on each horizontal（水平） and vertical （垂直）line), so it is O(N^2 log N). It also illustrates the use of
enums in Java (sorry).

[提交][状态]