我遇到了一个涉及路径查找的Google Foobar问题，但是我的解决方案无法通过2个测试用例，这些输入和输出被隐藏。
问题描述：
你有一些空间站的地图，每个地图都从监狱出口开始并以逃生舱门结束。地图由0和1的矩阵表示，其中0表示可通过的空间，1表示不可通过的墙壁。监狱的出口在左上角（0,0），逃生舱门在右下角（w-1,h-1）。
编写一个函数answer(map)，生成从监狱门到逃生舱门的最短路径长度，其中您可以删除一堵墙作为改造计划的一部分。路径长度是您通过的节点总数，包括入口和出口节点。起始和结束位置始终可通过（0）。地图始终是可解的，尽管您可能需要删除墙壁。地图的高度和宽度可以从2到20。只能进行基本方向的移动；不允许对角线移动。
测试用例
输入:
(int) maze = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]输出:
(int) 7输入:
(int) maze = [[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]]输出:
(int) 11
我的代码：
from queue import PriorityQueue
# Grid class
class Grid:
# Initialized with dimensions to check later if all neighbor points are actually within the graph
def __init__(self, width, height):
self.width = width
self.height = height
self.walls = []
self.weights = {}
self.wall_count = 0
# Find the cost of a certain destination node
# Cost is reported as a tuple to account for going across a wall: (# of moves through a wall, # of normal moves)
def cost(self, from_node, to_node):
if to_node in self.walls:
return self.weights.get(to_node, (1, 0))
else:
return self.weights.get(to_node, (0, 1))
# Check if the location is actually within the graph
def in_bounds(self, id):
(x, y) = id
return 0 <= x < self.width and 0 <= y < self.height
# Find the adjacent nodes of a node (ie. the places it can go to)
# Filters out any result which isn't on the graph using self.in_bounds
def neighbors(self, id):
(x, y) = id
results = [(x+1, y), (x, y-1), (x-1, y), (x, y+1)]
if (x + y) % 2 == 0: results.reverse() # aesthetics
results = filter(self.in_bounds, results)
return results
# Find the dimensions of the 2D list by finding the lengths of the outer and inner lists
def dimensions_2d(xs):
width = len(xs)
height = len(xs[0])
return (width, height)
# Returns all the positions of an element in a 2D list
# In this case it's used to find all walls (occurences of 1) to pass to the Grid object
def index_2d(xs, v):
results = [(x, y) for y, ls in enumerate(xs) for x, item in enumerate(ls) if item == v]
return results
# Djikstra search algorithm; mistakenly named "a_star" before
# Returns both a dictionary of "destination" locations to "start" locations (tuples) as well as a dictionary of the calculated cost of each location on the grid
def djikstra_search(graph, start, goal):
# Priority Queue to select nodes from
frontier = PriorityQueue()
# Place our starting cost in
frontier.put(start, (0, 0))
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = (0, 0)
while not frontier.empty():
# Get the element with the highest priority from the queue
current = frontier.get()
if current == goal:
break
# For every neighbor of the selected node
for next in graph.neighbors(current):
# The new cost of the neighbor node is current cost plus cost of this node - (1, 0) if it goes through a wall, (0, 1) otherwise
new_cost = (cost_so_far[current][0] + graph.cost(current, next)[0], cost_so_far[current][1] + graph.cost(current, next)[1])
# If the node has not cost currently
# OR if the number of walls traveled through is less than the current cost
# AND if the number of normal steps taken is less than or the same as the current number
if next not in cost_so_far or (new_cost[0] < cost_so_far[next][0] and sum(new_cost) <= sum(cost_so_far[next])):
# Record it in both the cost and came_from dicts
cost_so_far[next] = new_cost
# Place the cost in the queue
priority = new_cost
frontier.put(next, priority)
came_from[next] = current
return came_from, cost_so_far
# Find the length of the calculated path
# Using the returned list of edges from djikstra_search, move backwards from the target end and increment the length until the start element is reached
def path(grid, start, end):
# Perform the search
path = djikstra_search(grid, start, end)
search = path[0]
# If the end element's cost travels through more than 1 wall return 0
if path[1].get(end)[0] > 1:
return 0
# Otherwise move backwards from the end element and increment length each time
# Once the start element has been reached, we have our final length
length = 1
last = end
while last != start:
last = search.get(last)
length += 1
return length
# The "main" function
def answer(maze):
# Find all occurences of walls (1) in the 2D list
walls = index_2d(maze, 1)
# Find the x and y dimensions of the maze (required for the Grid object)
dims = dimensions_2d(maze)
# Create a new grid with our found dimensions
grid = Grid(dims[0], dims[1])
# The start point will always be at (0,0) and the end will always be at the bottom-right so we define those here
start = (0, 0)
end = (dims[0] - 1, dims[1] - 1)
# the walls variable's locations are flipped, so reverse each of them to get the right wall positions
grid.walls = [(y, x) for x, y in walls]
# Return the length
return path(grid, start, end)
在我的测试中（网格大小最多为7x7），这个解决方案似乎没有问题。
非常感谢任何帮助（或失败的情况）！
