你在一个长方形的房间里遇到敌人，你只有一把激光武器，房间里没有任何障碍物，墙壁可以完全反射激光束。然而，激光只能传播一定的距离，然后就变得毫无用处，如果它撞到角落，它会沿着它来的方向反射回来。
这就是谜题的进行方式，您将获得自己所在位置和目标位置的坐标、房间尺寸以及光束可以传播的最大距离。例如，如果房间是 3 x 2，您的位置是 (1, 1)，目标是 (2, 1)，那么可能的解决方案是：
我尝试了以下方法，从源 (1, 1) 开始并以角度 0 弧度创建一个矢量，跟踪矢量路径和反射，直到它击中目标或矢量的总长度超过最大允许长度，重复以0.001弧度为间隔，直到完成一个完整的循环。这是我到目前为止的代码：
from math import *
UPRIGHT = 0
DOWNRIGHT = 1
DOWNLEFT = 2
UPLEFT = 3
UP = 4
RIGHT = 5
LEFT = 6
DOWN = 7
def roundDistance (a):
b = round (a * 100000)
return b / 100000.0
# only used for presenting and doesn't affect percision
def double (a):
b = round (a * 100)
if b / 100.0 == b: return int (b)
return b / 100.0
def roundAngle (a):
b = round (a * 1000)
return b / 1000.0
def isValid (point):
x,y = point
if x < 0 or x > width or y < 0 or y > height: return False
return True
def isCorner (point):
if point in corners: return True
return False
# Find the angle direction in relation to the origin (observer) point
def getDirection (a):
angle = roundAngle (a)
if angle == 0: return RIGHT
if angle > 0 and angle < pi / 2: return UPRIGHT
if angle == pi / 2: return UP
if angle > pi / 2 and angle < pi: return UPLEFT
if angle == pi: return LEFT
if angle > pi and angle < 3 * pi / 2: return DOWNLEFT
if angle == 3 * pi / 2: return DOWN
return DOWNRIGHT
# Measure reflected vector angle
def getReflectionAngle (tail, head):
v1 = (head[0] - tail[0], head[1] - tail[1])
vx,vy = v1
n = (0, 0)
# Determin the normal vector from the tail's position on the borders
if head[0] == 0: n = (1, 0)
if head[0] == width: n = (-1, 0)
if head[1] == 0: n = (0, 1)
if head[1] == height: n = (0, -1)
nx,ny = n
# Calculate the reflection vector using the formula:
# r = v - 2(v.n)n
r = (vx * (1 - 2 * nx * nx), vy * (1 - 2 * ny * ny))
# calculating the angle of the reflection vector using it's a and b values
# if b (adjacent) is zero that means the angle is either pi/2 or -pi/2
if r[0] == 0:
return pi / 2 if r[1] >= 0 else 3 * pi / 2
return (atan2 (r[1], r[0]) + (2 * pi)) % (2 * pi)
# Find the intersection point between the vector and borders
def getIntersection (tail, angle):
if angle < 0:
print "Negative angle: %f" % angle
direction = getDirection (angle)
if direction in [UP, RIGHT, LEFT, DOWN]: return None
borderX, borderY = corners[direction]
x0,y0 = tail
opp = borderY - tail[1]
adj = borderX - tail[0]
p1 = (x0 + opp / tan (angle), borderY)
p2 = (borderX, y0 + adj * tan (angle))
if isValid (p1) and isValid (p2):
print "Both intersections are valid: ", p1, p2
if isValid (p1) and p1 != tail: return p1
if isValid (p2) and p2 != tail: return p2
return None
# Check if the vector pass through the target point
def isHit (tail, head):
d = calcDistance (tail, head)
d1 = calcDistance (target, head)
d2 = calcDistance (target, tail)
return roundDistance (d) == roundDistance (d1 + d2)
# Measure distance between two points
def calcDistance (p1, p2):
x1,y1 = p1
x2,y2 = p2
return ((y2 - y1)**2 + (x2 - x1)**2)**0.5
# Trace the vector path and reflections and check if it can hit the target
def rayTrace (point, angle):
path = []
length = 0
tail = point
path.append ([tail, round (degrees (angle))])
while length < maxLength:
head = getIntersection (tail, angle)
if head is None:
#print "Direct reflection at angle (%d)" % angle
return None
length += calcDistance (tail, head)
if isHit (tail, head) and length <= maxLength:
path.append ([target])
return [path, double (length)]
if isCorner (head):
#print "Corner reflection at (%d, %d)" % (head[0], head[1])
return None
p = (double (head[0]), double (head[1]))
path.append ([p, double (degrees (angle))])
angle = getReflectionAngle (tail, head)
tail = head
return None
def solve (w, h, po, pt, m):
# Initialize global variables
global width, height, origin, target, maxLength, corners, borders
width = w
height = h
origin = po
target = pt
maxLength = m
corners = [(w, h), (w, 0), (0, 0), (0, h)]
angle = 0
solutions = []
# Loop in anti-clockwise direction for one cycle
while angle < 2 * pi:
angle += 0.001
path = rayTrace (origin, angle)
if path is not None:
# extract only the points coordinates
route = [x[0] for x in path[0]]
if route not in solutions:
solutions.append (route)
print path
# Anser is 7
solve (3, 2, (1, 1), (2, 1), 4)
# Answer is 9
#solve (300, 275, (150, 150), (185, 100), 500)
该代码以某种方式工作，但它没有找到所有可能的解决方案，我有一个很大的精度问题，我不知道在比较距离或角度时应该考虑多少位小数。我不确定这是否是正确的方法，但这是我能做到的最好的方法。
如何修复我的代码以提取所有解决方案？我需要它高效，因为房间可能会变得很大（500 x 500）。有没有更好的方法或者某种算法来做到这一点？
