在谷歌挑战矩阵中寻找可能的最短路径

Question

我一直在尝试谷歌的挑战，但在这一点上遇到了困难。我已经写了一些代码来解决这个问题，它给了我正确的结果，但有一个隐藏的测试，我失败了，我一直在思考，无法找到答案。我试图给出一个整数来验证，结果发现答案应该是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步额外跨过拆除的墙壁

这将给出相同的结果，但程序不必每次搜索整个路径，只需在开始时搜索两次