问题 24735. -- 【USACO2013JAN】镜子{Bronze题1}

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

时间限制: 1 Sec  内存限制: 128 MB
献花: 6  解决: 4
[献花][花圈]

题目描述

1.镜子{Bronze1}

【问题描述】

农民约翰安装了N(1 <= N <= 200)个带有反光镜的栅栏,他希望从他的坐标为(0,0)的家中看到坐标为(a,b)的牛的情况。

栅栏在整数坐标(x_i, y_i),形状是'/'或者'\'的45度线段,比如坐标(3,5)的'/'形栅栏可以被描述成(2.9,4.9) 到 (3.1,5.1)的线段。每个栅栏位于不同的位置,坐标范围是[-1,000,000..1,000,000],(0,0) 和(a,b).处没有栅栏。

农民约翰位于(0,0),面朝+X方向,他希望通过栅栏上反光镜看到(a,b)的情况。不幸的是,他可能放错了其中的一个反光镜的形状,请找出并调整这个镜子,使得他能够顺利地看到(a,b)的牛的情况。

【文件输入】

第一行为三个整数N,a,b。

接下来2..N+1行,每行三个整数,分别表示坐标和形状。

【文件输出】

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

【输入样例】

5 6 2

3 0 /

0 2 /

1 2 /

3 2 \

1 3 \

【输出样例】

4

【样例说明】

将坐标为(3,2)的反光镜从\调整为/。

输入

输出

提示


注意的N只有200O(N3)的复杂度可以承受。



模拟,检查当前是否可以看到终点,如果不行,则依次翻转每个镜子,并检查。如果没有一个可行,则无解。



检查也是一个模拟的过程,根据当前位置和方向,找到下一个该方向的镜子。



判断是否出界,或者是否出现循环.




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).






来源

[献花][花圈]