Мне не удается решить вопрос 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 случая, которые я ввел, но не проходит один из скрытых случаев. Я считаю, что это связано с ошибкой превышения лимита времени, но это также может быть ошибка правильности. Будем признательны за любые отзывы о том, как улучшить мой код.