準備兔子逃生-Foobar

我已經有一段時間了，在我的一生中，我無法弄清楚為什么我不能通過測驗用例 4 和 5。我的代碼如下，包括我自己的自定義測驗用例，它們都在 5 毫秒內執行和通過。

基本上，我為每個節點的位置添加了第三個維度，表示是否已經穿過墻壁。在分析每個當前節點的鄰居時，如果它是一面墻，并且當前節點的第三個坐標為零，那么移動到墻和第三個坐標上的 1 成為一種選擇。在紙上，它作業得很好。在我自己的 IDE 中，它作業得很好。

我開始懷疑這里是否有 Python 3 并且在 foobar 或其他東西中無法正常作業。我會很感激任何幫助。

class Node():
    def __init__(self, position):
        self.position = position
        
        self.gCost = 1
        self.hCost = 0
        self.fCost = 0
    
    def __eq__(self, other):
        return self.position == other.position


def solution(map):
    
    startNode = Node((0, 0, 0))
    endNode = Node((len(map[0]) - 1, len(map) - 1, 0))
    
    openList = [startNode]
    closedList = []

    while openList:
        currentNode = openList[0]
        currentIndex = 0

        for i in range(len(openList)):
            if openList[i].fCost < currentNode.fCost:
                currentNode = openList[i]
                currentIndex = i
        
        openList.pop(currentIndex)
        closedList.append(currentNode)

        if currentNode.position[0] == endNode.position[0] and currentNode.position[1] == endNode.position[1]:
            return currentNode.gCost

        for offset in [(1, 0), (-1, 0), (0, 1), (0, -1)]:

            neighborPosition = (currentNode.position[0]   offset[0], currentNode.position[1]   offset[1], currentNode.position[2])

            if neighborPosition[0] < 0 or neighborPosition[0] >= len(map[0]) or neighborPosition[1] < 0 or neighborPosition[1] >= len(map):
                continue

            if map[neighborPosition[0]][neighborPosition[1]] == 1:
                if currentNode.position[2] == 1:
                    continue
                neighborPosition = (neighborPosition[0], neighborPosition[1], 1)

            neighbor = Node(neighborPosition)

            if neighbor in closedList: 
                continue
            
            if neighbor in openList:

                openNodeIndex = openList.index(neighbor)
                if openList[openNodeIndex].gCost < currentNode.gCost   1:
                    continue
                openList.pop(openNodeIndex)
                openList.append(neighbor)

            else:
                openList.append(neighbor)

            neighbor.gCost = currentNode.gCost   1
            neighbor.hCost = endNode.position[0] - neighbor.position[0]   endNode.position[1] - neighbor.position[1]
            neighbor.fCost = neighbor.gCost   neighbor.hCost

    
    return -1

import time

start = time.time()
map1 = [[0, 0, 0, 1], [1, 0, 0, 1], [1, 0, 0, 0], [0, 0, 0, 0]]
sol1 = solution(map1)
print("Result: ", sol1, "Expected: ", 7)
map2 = [[0,1,0,0,0], [0,1,0,1,0], [0,1,0,1,0], [0,1,0,1,0], [0,0,0,1,0]]
sol2 = solution(map2)
print("Result: ", sol2, "Expected: ", 9) 
map3 = [[0,0,0,0,0,0,1,0,0,0], [0,0,0,0,1,0,1,0,1,0], [0,0,0,0,1,0,1,0,1,0], [0,0,0,0,1,0,1,0,1,0], [0,0,0,0,1,0,1,0,1,0], [0,0,0,0,1,0,1,0,1,0], [0,0,0,0,1,0,1,0,1,0], [0,0,0,0,1,0,1,0,1,0], [0,0,0,0,1,0,1,0,1,0], [0,0,0,0,1,0,0,0,1,0]]
sol3 = solution(map3)
print("Result: ", sol3, "Expected: ", 19)
map4 = [[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]]
sol4 = solution(map4)
print("Result: ", sol4, "Expected: ", 11)
map5 = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]
sol5 = solution(map5)
print("Result: ", sol5, "Expected: ", 7)
map6 = [[0,1,0], [0,1,0], [0,1,0]]
sol6 = solution(map6)
print("Result: ", sol6, "Expected: ", 5)
map7 = [[0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,0,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,1,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,1,0], [0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,1,1,0]]
sol7 = solution(map7)
print("Result: ", sol7, "Expected: ", 123)
map8 = [[0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0],[0,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0],[0,1,0,1,0,1,1,1,0,1,1,0,1,1,1,1,1,1,0,1],[0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0],[0,1,0,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1],[0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,0],[0,1,0,1,0,1,0,1,0,0,0,1,1,1,0,1,1,1,1,1],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,0],[1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0],[0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,0,1,1,1,1],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,1,1,0,0]]
sol8 = solution(map8)
print("Result: ", sol8, "Expected: ", 89)

end = time.time()
print("Time: ", end - start)

編輯：快速更新 - 將 closedList 轉換為一個集合，現在它在 1 毫秒內解決了我的測驗用例，盡管谷歌的測驗用例 4 和 5 仍然失敗。

uj5u.com熱心網友回復：

所以我想通了。線

if map[neighborPosition[0]][neighborPosition[1]] == 1:

x 和 y 坐標向后。應該是

if map[neighborPosition[1]][neighborPosition[0]] == 1:

在地圖不是正方形的情況下，它會超出范圍。只需要添加一個不方形的測驗用例并從那里很快弄清楚。

標籤：算法 寻找路径

上一篇：識別矩陣每一行中的最小元素

下一篇：將字串拆分為Vec<String>在字符處的最佳方法，當沒有其他字符之前沒有在Rust中進行環視時？