class Queue:
    def __init__(self):
        self._queue = []
        self._count = 0
        self._first_element = 0

    def enqueue(self, value):
        self._queue.append(value)
        self._count += 1

    def dequeue(self):
        if self._count > 0:
            self._first_element += 1
            self._count -= 1
        else:
            raise Exception("Empty array")

    def peek(self):
        if self._count > 0:
            return self._queue[self._first_element]
        else:
            raise Exception("Empty array")

    def empty(self):
        return self._count == 0


def reverse_maze(maze):
    new_maze = []
    for i in range(len(maze) - 1, -1, -1):
        temp_array = []
        for j in range(len(maze[i]) - 1, -1, -1):
            temp_array.append(maze[i][j])
        new_maze.append(temp_array)
    return new_maze


directions = [
    [+1, 0],  # Down
    [0, +1],  # Right
    [-1, 0],  # Up
    [0, -1]  # Left
]


def create_matrix(map):
    matrix = []
    for i in range(len(map)):
        matrix.append([-1] * len(map[i]))
    return matrix


def solve(map, miner, exit):
    map = reverse_maze(map)

    if len(map[0]) > 1:
        miner['x'], miner['y'] = miner['y'], miner['x']
        exit['x'], exit['y'] = exit['y'], exit['x']

    check = create_matrix(map)

    queue = Queue()
    queue.enqueue([exit["x"], exit["y"]])
    print(exit['x'])
    print(exit['y'])
    check[exit["x"]][exit["y"]] = 0

    while not queue.empty():
        x = queue.peek()[0]
        y = queue.peek()[1]

        for i in range(4):
            new_x = x + directions[i][0]
            new_y = y + directions[i][1]

            if 0 <= new_x < len(map) and 0 <= new_y < len(map[0]) and map[new_x][new_y] and check[new_x][new_y] == -1:
                queue.enqueue([new_x, new_y])
                check[new_x][new_y] = check[x][y] + 1

        queue.dequeue()

    coordenates = [miner['x'], miner['y']]
    answer = []
    min_value = check[coordenates[0]][coordenates[1]]
    while min_value != 0:
        temp_mov = ''
        new_x = 0
        new_y = 0
        for i in range(4):
            x = coordenates[0] + directions[i][0]
            y = coordenates[1] + directions[i][1]

            if 0 <= x < len(map) and 0 <= y < len(map[0]) and check[x][y] != -1 and check[x][y] < min_value:
                min_value = check[x][y]
                if i == 0:
                    if len(map[0]) == 1:
                        temp_mov = "right"
                    else:
                        temp_mov = "down"
                elif i == 1:
                    temp_mov = "right"
                elif i == 2:
                    if len(map[0]) == 1:
                        temp_mov = "left"
                    else:
                        temp_mov = "up"
                else:
                    temp_mov = "left"
                new_x = x
                new_y = y

        answer.append(temp_mov)
        coordenates = [new_x, new_y]

    return answer