# Feel free to add more classes/helper functions if you like, code quality counts!
import queue

class RobotRouter:
    # This class will be initialized with the map features from the problem input.
    # barriers and laserCoordinates are arrays of Coordinate objects.
    # laserDirections is an array of strings representing the direction of
    # the corresponding laser in laserCoordinates.
    def __init__(self, barriers, laserCoordinates, laserDirections):
        self.barriers = set(barriers)
        self.lasers = instantiateLasers(barriers, laserCoordinates, laserDirections)

    # This method will be called to get your optimal route.
    # origin and destination are Coordinate objects (with x and y properties)
    # It should return a list of Coordinate objects,
    # starting with the origin and ending with the destination.
    # If you could not find a valid route, return an empty list.
    def route(self, origin, destination):
        nodes = queue.Queue()
        visited = {}
        prev = {}
        prev[origin] = origin
        nodes.put(origin)

        while not nodes.empty():
            lastnode = nodes.get()
            visited[lastnode] = True

            if lastnode == destination:
                # generating the path to return
                pathnode = lastnode
                path = []
                while prev[pathnode] != pathnode:
                    path.append(pathnode)
                    pathnode = prev[pathnode]

                path.append(pathnode)
                return path[::-1]


            up = Coordinate(lastnode.x, lastnode.y + 1)
            down = Coordinate(lastnode.x, lastnode.y - 1)
            right = Coordinate(lastnode.x + 1, lastnode.y)
            left = Coordinate(lastnode.x - 1, lastnode.y)

            if self.isAccessible(up) and up not in visited:
                nodes.put(up)
                prev[up] = lastnode
            if self.isAccessible(down) and down not in visited:
                nodes.put(down)
                prev[down] = lastnode
            if self.isAccessible(right) and right not in visited:
                nodes.put(right)
                prev[right] = lastnode
            if self.isAccessible(left) and left not in visited:
                nodes.put(left)
                prev[left] = lastnode

        return []

    def isAccessible(self, coordinate):
        if coordinate in self.barriers:
            return False
        for laser in self.lasers:
            if laser.hits(coordinate):
                return False

        return True

def instantiateLasers(barriers, laserCoordinates, laserDirections):
    lasers = []
    for i in range(len(laserCoordinates)):
        origin = laserCoordinates[i]
        direction = laserDirections[i]
        laser = Laser(origin, direction)
        lasers.append(laser)
        for barrier in barriers:
            if direction == "N" and barrier.y > origin.y:
                if laser.limit == None:
                    laser.limit = barrier
                else:
                    laser.limit = Coordinate(origin.x, min(laser.limit.y, barrier.y))
            if direction == "S" and barrier.y < origin.y:
                if laser.limit == None:
                    laser.limit = barrier
                else:
                    laser.limit = Coordinate(origin.x, max(laser.limit.y, barrier.y))
            if direction == "E" and barrier.x > origin.x:
                if laser.limit == None:
                    laser.limit = barrier
                else:
                    laser.limit = Coordinate(min(laser.limit.x, barrier.x), barrier.y)
            if direction == "W" and barrier.x < origin.x:
                if laser.limit == None:
                    laser.limit = barrier
                else:
                    laser.limit = Coordinate(max(laser.limit.x, barrier.x), barrier.y)

    return lasers


class Laser:
    def __init__(self, origin, direction, limit = None):
        self.origin = origin
        self.direction = direction
        self.limit = limit

    def hits(self, coord):
        if self.direction == "N":
            if coord.x == self.origin.x and coord.y >= self.origin.y:
                if self.limit == None:
                    return True
                if self.limit != None and coord.y < self.limit.y:
                    return True
            return False
        elif self.direction == "S":
            if coord.x == self.origin.x and coord.y <= self.origin.y:
                if self.limit == None:
                    return True
                if self.limit != None and coord.y > self.limit.y:
                    return True
            return False
        elif self.direction == "E":
            if coord.y == self.origin.y and coord.x >= self.origin.x:
                if self.limit == None:
                    return True
                if self.limit != None and coord.x < self.limit.x:
                    return True
            return False
        else:
            if coord.y == self.origin.y and coord.x <= self.origin.x:
                if self.limit == None:
                    return True
                if self.limit != None and coord.x > self.limit.x:
                    return True
            return False