准备兔子逃脱 - Foobar

Question

我在这方面已经有一段时间了，我一直想不通为什么我不能通过测试用例 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 毫秒内解决了我的测试用例，但仍然失败了 Google 的测试用例 4 和 5。

Answer 1

所以我想通了。行

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

x 和 y 坐标向后。应该是

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

如果地图不是方形的，那就是越界了。只需要添加一个不是正方形的测试用例，然后从那里很快就弄明白了。

准备兔子逃脱 - Foobar

Prepare the Bunnies Escape - Foobar

algorithm

path-finding