Проблема Google Foobar: кратчайший путь, по которому можно убрать стену [closed]

Мне не удается решить вопрос Google Foobar, связанный с поиском пути. Мое решение не проходит 1 тестовый пример, входы и выходы которого скрыты.

Подсказка

У вас есть карты частей космической станции, каждая из которых начинается у выхода из рабочей зоны и заканчивается у двери в спасательную капсулу. Карта представлена ​​в виде матрицы из 0 и 1, где 0 — проходимое пространство, а 1 — непроходимые стены. Дверь из станции находится вверху слева (0,0), а дверь в спасательную капсулу — внизу справа (w-1, h-1).

Напишите функциональное решение (карту), которое генерирует длину кратчайшего пути от двери станции до спасательной капсулы, где вам разрешено удалить одну стену в рамках ваших планов реконструкции. Длина пути — это общее количество узлов, через которые вы проходите, с учетом как входных, так и выходных узлов. Начальная и конечная позиции всегда проходимы (0). Карта всегда будет разрешима, хотя вам может понадобиться убрать стену, а может и нет. Высота и ширина карты могут быть от 2 до 20. Ходы можно делать только по сторонам света; диагональные ходы не допускаются.

Случаи

Вход: решение ([[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]])

Выход: 7

Вход: решение ([[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0]])

Выход: 11

А вот мой код:

from math import sqrt, ceil

class Node:
    '''
    Class for nodes
    '''
    def __init__(self, parent = None, position= None):
        '''
        initialize the object
        '''
        self.parent = parent
        self.position = position

        self.g = 1
        self.h = 0
        self.f = 0
        self.wall_broken = False
    
    def __eq__(self, other):
        '''
        works for equality chacks
        '''
        return ((self.position == other.position) and (self.wall_broken == other.wall_broken))
    
    def __repr__(self):
        '''
        for printing the object
        '''
        return 'Position: {} Wall_Broken: {}'.format(self.position, self.wall_broken)
    
def solution(maze):
    '''
    A* algorithm implementation
    '''
    # The starting and ending position is always left top and right bottom respectively
    start_pos = (0,0)
    l = len(maze)
    w = len(maze[0])
    end_pos = (l-1, w-1)

    # Create the start and end node
    start = Node(position=start_pos)
    end = Node(position=end_pos)

    # Yet to visit and Visited list
    yet_to_visit = []
    visited = []

    # Keep start in yet to visit
    yet_to_visit.append(start)

    while yet_to_visit:
        # Loop untill we completely search all nodes

        # We need the lowest f in current node
        current_node = yet_to_visit[0]
        for node in yet_to_visit:
            if current_node.f > node.f:
                current_node = node
        
        # Remove the current node from yet_to_visit
        yet_to_visit.remove(current_node)
        # Add the current node to the visited
        visited.append(current_node)

        # Check if current node is goal or not
        if current_node.position == end.position:
            return int(current_node.f)

        # Generate children
        children = []
        for position in [(0,1), (0,-1), (1,0), (-1,0)]:
            new_position = (current_node.position[0] + position[0], current_node.position[1] + position[1])
            # Check the validity of borders
            if new_position[0] < 0 or new_position[0] >= l or new_position[1] < 0 or new_position[1] >= w:
                continue

            # Check if wall
            if maze[new_position[0]][new_position[1]] == 1:
                # Check if path has wall broken
                if current_node.wall_broken:
                    # Wall has been broken
                    continue
                else:
                    # Wall has not been broken
                    # check if visited
                    check = Node(current_node, new_position)
                    check.wall_broken = True
                    flag = 0
                    for visited_nodes in visited:
                        if check == visited_nodes:
                            flag = 1
                            break
                    if flag == 0:
                        children.append(check)
                    continue
            
            # Check if already visited
            flag = 0
            check = Node(current_node, new_position)
            check.wall_broken = current_node.wall_broken
            for visited_nodes in visited:
                if check == visited_nodes:
                    flag = 1
                    break
            if flag == 1:
                continue
            
            # If all the above things are not True
            children.append(check)
        
        # Iterate over children to consider the yet_to_visit
        for child in children:
            # Heuristics
            child.g = current_node.g + 1
            child.h = end.position[0] - child.position[0] + (end.position[1] - child.position[1])
            child.f = child.g + child.h

            # Check if child in open list
            for idx, open_node in enumerate(yet_to_visit):
                if open_node == child:
                    # check for the path measure
                    if open_node.g > child.g:
                        yet_to_visit[idx] = child
                    continue
            
            # Add the node to yet_to_visit
            yet_to_visit.append(child)

print(solution(
    [[0,0,0,0,0,0],
    [1,1,1,1,0,1],
    [0,0,0,0,0,0],
    [0,0,1,1,1,1],
    [0,1,1,1,1,1],
    [0,0,0,0,0,0]]
))

print(solution(
    [[0, 1, 1, 0],
    [0, 0, 0, 1],
    [1, 1, 0, 0],
    [1, 1, 1, 0]]
))

Он проходит 2 случая, которые я ввел, но не проходит один из скрытых случаев. Я считаю, что это связано с ошибкой превышения лимита времени, но это также может быть ошибка правильности. Будем признательны за любые отзывы о том, как улучшить мой код.

0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *