python - 在 google 挑战的矩阵中找到可能的最短路径
问题描述
我一直在尝试这些谷歌挑战并被困在这个挑战上。我已经编写了一些代码来解决这个问题，它给了我正确的结果，但是有一个隐藏的测试我失败了，我一直在考虑它并且找不到答案。我试图给出一个整数答案来验证，发现答案应该是 66。但由于某种原因，我无法找到我犯错的地方。作为一个自学的新程序员，任何帮助将不胜感激。寻找使我的代码更高效的想法以及关于隐藏测试可能存在什么问题的任何想法。
编写一个函数解决方案（地图），生成从车站门到逃生舱的最短路径长度，作为改造计划的一部分，您可以在其中拆除一堵墙。路径长度是您通过的节点总数，包括入口节点和出口节点。起始位置和结束位置始终可以通过 (0)。尽管您可能需要也可能不需要移除墙壁，但地图始终是可解的。地图的高度和宽度可以从 2 到 20。移动只能在基本方向上进行；不允许对角线移动。
def distanceMap(Map):
notVisited = {}
distances = {}
for i in range(len(Map)):
for j in range(len(Map[0])):
index = str(i)+str(j)
notVisited[index] = None
distances[index] = {}
if i+1 < len(Map):
distances[index].update({str(i+1)+str(j):1 if Map[i+1][j] == 0 else 10000})
if j+1 < len(Map[0]):
distances[index].update({str(i)+str(j+1): 1 if Map[i][j+1] == 0 else 10000})
if i-1 >= 0:
distances[index].update({str(i-1)+str(j): 1 if Map[i-1][j] == 0 else 10000})
if j-1 >= 0:
distances[index].update({str(i)+str(j-1): 1 if Map[i][j-1] == 0 else 10000})
return(notVisited,distances)
def shortestPath(notVisited,distances,width,height):
visited = {}
current = '00'
distance = 1
notVisited[current] = distance
target = False
while target != True:
for neighbour, cost in distances[current].items():
if neighbour in visited: continue
newDistance = distance + cost
if notVisited[neighbour] == None or notVisited[neighbour] > newDistance: notVisited[neighbour] = newDistance
visited[current] = distance
del notVisited[current]
candidates = [node for node in notVisited.items() if node[1]]
current, distance = sorted(candidates, key=lambda x: x[1])[0]
if current == height+width: target = True
return(notVisited[height+width])
def solution(Map):
if len(Map[0]) > 20 or len(Map[0]) < 2 or len(Map) > 20 or len(Map) < 2: return 'invalid map'
width = str(len(Map[0]) - 1)
height = str(len(Map)-1)
notVisited,distances = distanceMap(Map)
shortestDist = []
shortestDist.append(shortestPath(notVisited,distances,width,height))
for i in range(len(Map)):
for j in range(len(Map[0])):
neighbours = 0
if Map[i][j] == 1:
if i+1 < len(Map) and Map[i+1][j] == 0: neighbours += 1
if j+1 < len(Map[0]) and Map[i][j+1] == 0: neighbours += 1
if i-1 >= 0 and Map[i-1][j] == 0: neighbours += 1
if j-1 >= 0 and Map[i][j-1] == 0: neighbours += 1
if neighbours > 1:
Map[i][j] = 0
notVisited, distances = distanceMap(Map)
shortestDist.append(shortestPath(notVisited,distances,width,height))
Map[i][j] = 1
shortest = sorted(shortestDist)[0]
if shortest == len(Map)+len(Map[0])-1: return(shortest)
if shortest > 10000: return('not solvable')
return(shortest)
maze = [
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0],
[1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
[1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0],
[0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0],
[1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
print(solution(maze))
我能够完成挑战，这是我最后的提交
def createGraph(Map,height,width):
graph = {}
walls = []
for i in range(height):
for j in range(width):
index = (i, j)
graph[index] = []
if Map[i][j] != 1:
if i+1 < height:
if Map[i+1][j] == 0: graph[index].append((i+1, j))
if i-1 >= 0:
if Map[i-1][j] == 0: graph[index].append((i-1, j))
if j+1 < width:
if Map[i][j+1] == 0: graph[index].append((i, j+1))
if j-1 >= 0:
if Map[i][j-1] == 0: graph[index].append((i, j-1))
else: walls.append((i,j))
return(graph,walls)
def removableWalls(Map,walls,height,width):
wallsRemovable = []
for x in range(len(walls)):
i = walls[x][0]
j = walls[x][1]
passableNeighbours = 0
if i+1 < height:
if Map[i+1][j] == 0: passableNeighbours += 1
if i-1 >= 0:
if Map[i-1][j] == 0: passableNeighbours += 1
if j+1 < width:
if Map[i][j+1] == 0:passableNeighbours += 1
if j-1 >= 0:
if Map[i][j-1] == 0: passableNeighbours += 1
if passableNeighbours > 1:wallsRemovable.append(walls[x])
return wallsRemovable
def findPath(graph,start,finish):
visited = []
queue = []
distances = {}
distances[start] = 1
queue.append(start)
visited.append((0, 0))
while queue:
node = queue.pop(0)
for neighbour in graph[node]:
if neighbour not in visited:
visited.append(neighbour)
queue.append(neighbour)
distances[neighbour] = distances[node]+1
if (finish) not in visited:
return('solution not found')
return(distances[finish])
def solution(Map):
if len(Map[0]) > 20 or len(Map[0]) < 2 or len(Map) > 20 or len(Map) < 2: return 'invalid map'
shortest = []
width = len(Map[0])
height = len(Map)
graph,wallList = createGraph(Map,height,width)
shortest.append(findPath(graph,(0,0),(height-1,width-1)))
walls = removableWalls(Map, wallList, height, width)
for x in range(len(walls)):
i = walls[x][0]
j = walls[x][1]
Map[i][j] = 0
graph = createGraph(Map, height, width)[0]
shortest.append(findPath(graph,(0,0),(height-1,width-1)))
Map[i][j] = 1
if min(shortest) == height+width-1: return min(shortest)
return min(shortest)
# Map = [[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
# [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1],
# [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0],
# [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0],
# [1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
# [1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
# [0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0],
# [0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0],
# [1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
# [1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
# [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
# [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
# Map = [[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]]
print(solution(Map))
但是，我想将来在代码中再做一件事。计算从开始到结束的路径并保存到所有节点的距离，然后从完成到开始执行相同的操作。然后移除在其一侧以上有路径的墙壁，并添加邻居的距离：
迷宫的新解决方案 = 邻居距离起点 1 距离 + 邻居距离终点 2 距离 + 1 个额外步骤以穿过拆除的墙壁
这将给出相同的结果，但程序不必每次都搜索整个路径，而只需在开始时搜索两次。
解决方案
推荐阅读
- android - 从 RecyclerView.Adapter 类更新列表数据中的某些项目
- c# - 列“zone_id”不存在
- design-patterns - 编写正确的 DSL
- javascript - 如何根据下拉选择动态地重新措辞文本
- c++ - 如何使用模板元编程在 C++17 中将一种类型转换为另一种类型？
- python - 刮取数据而不重复已保存的数据
- css - css 响应式布局 - 如何避免第二行中的单个项目？
- google-cloud-dataflow - 在批处理管道中，如何为批处理源中的数据分配时间戳，例如 Beam 管道中的 csv 文件
- php - 如何在中间件之前运行 Laravel 路由约束？
- sql-server - 显示所有员工最近的分配