你在一个长方形的房间内面对一个敌人,你只有一个激光束武器,房间里没有障碍物,墙壁可以完全反射激光束.然而,激光只能在它变得无用之前行进一定距离,如果它碰到一个角落,它会以相同的方向反射回来.

这就是拼图的方式,你会得到你所在位置的坐标和目标的位置,房间尺寸以及光束可以行进的最大距离.例如,如果房间是3乘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,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,4)

# Answer is 9
#solve (300,275,(150,150),(185,100),500)

代码以某种方式工作,但它没有找到所有可能的解决方案,我有一个很大的精度问题,我不知道在比较距离或角度时我应该考虑多少小数.我不确定这是正确的做法,但这是我能做到的最好的方式.

如何修复我的代码以提取所有解决方案？我需要它才能有效,因为房间可以变得非常大(500 x 500).有没有更好的方法或者某种算法来做到这一点？