我正在尝试解决《代码到来》第 17 天第 2 部分。我得到了第 1 部分的正确答案，但当我修改以解决 P2 时，我得到了错误的输入答案

Question

我对为什么我的答案是错误的感到有点恼火，因为它通过了他们提供的测试用例的输出。这是问题的链接https://adventofcode.com/2023/day/17

任何人都可以尝试建议我我在这里做错了什么吗？我真的不知道我做错了什么，因为一切似乎都是正确的。

from copy import deepcopy
from heapq import heappush, heappop

pInput = [
    [int(char) for char in list(line.replace("\n", ""))]
    for line in open("input.txt", "r")
]
width, height = len(pInput[0]), len(pInput)


def maxStepsReached(steps):
    return steps > 10


def isOOB(y, x):
    return not (0 <= y < len(pInput) and 0 <= x < len(pInput[0]))


def expand_helper(node, dy, dx, dir, res):
    new_y = node[1] + dy
    new_x = node[2] + dx
    if isOOB(new_y, new_x) or dir == node[3] and maxStepsReached(node[4] + 1):
        return res
    if dir == node[3]:
        res.append((node[0] + pInput[new_y][new_x], new_y, new_x, dir, node[4] + 1))
    elif node[4] >= 4:
        res.append((node[0] + pInput[new_y][new_x], new_y, new_x, dir, 1))
    return res


def expand(node):
    res = []
    if node[3] == ">":
        for dy, dx, dir in [[0, 1, ">"], [-1, 0, "A"], [1, 0, "V"]]:
            res = expand_helper(node, dy, dx, dir, res)
    elif node[3] == "<":
        for dy, dx, dir in [[0, -1, "<"], [-1, 0, "A"], [1, 0, "V"]]:
            res = expand_helper(node, dy, dx, dir, res)
    elif node[3] == "A":
        for dy, dx, dir in [[-1, 0, "A"], [0, 1, ">"], [0, -1, "<"]]:
            res = expand_helper(node, dy, dx, dir, res)
    elif node[3] == "V":
        for dy, dx, dir in [[1, 0, "V"], [0, 1, ">"], [0, -1, "<"]]:
            res = expand_helper(node, dy, dx, dir, res)
    return res


def ucs():
    closed = set()
    open = []
    heappush(open, (0, 0, 0, ">", 1))

    while open:
        node = heappop(open)
        if node[1] == height - 1 and node[2] == width - 1 and node[4] >= 4:
            return node[0]
        if (node[1], node[2], node[3], node[4]) in closed:
            continue
        closed.add((node[1], node[2], node[3], node[4]))
        successors = expand(node)
        for s in successors:
            heappush(open, s)

    return -1


print(ucs())

Answer 1

我稍微简化了你的代码，但没有改变设计。这仍然会根据我的输入产生正确的结果。

from heapq import heappush, heappop

pInput = [[int(char) for char in list(line.replace("\n", ""))] for line in open("day17.txt", "r")]
width, height = len(pInput[0]), len(pInput)

def maxStepsReached(steps):
    return steps > 10

def isOOB(y, x):
   return not (0 <= y < len(pInput) and 0 <= x < len(pInput[0]))

alldirs = ((0,1,'>'),(0,-1,'<'),(1,0,'V'),(-1,0,'A'))
opposite = {a:b for a,b in zip('<>AV','><VA')}

def expand(node):
    score, y, x, d, c = node
    res = []
    for dy, dx, dir in alldirs:
        if d == opposite[dir]:
            continue
        new_y = y + dy 
        new_x = x + dx 
        if isOOB(new_y, new_x):
            continue
        if dir == d:
            if maxStepsReached(c + 1):
                continue
            res.append((score + pInput[new_y][new_x], new_y, new_x, dir, c + 1))
        else:
            if c >= 4:
                res.append((score + pInput[new_y][new_x], new_y, new_x, dir, 1))
    return res 


def ucs():
    closed = set()
    open = []
    heappush(open, (0, 0, 0, '>', 1))
    heappush(open, (0, 0, 0, 'V', 1))
    heappush(open, (0, 0, 0, 'A', 1))
    heappush(open, (0, 0, 0, '<', 1))

    while open:
        node = heappop(open)
        if node[1] == height - 1 and node[2] == width - 1 and node[4] >= 4: 
            return node[0]
        if (node[1], node[2], node[3], node[4]) in closed:
            continue
        closed.add((node[1], node[2], node[3], node[4]))
        successors = expand(node)
        for s in successors:
            heappush(open, s)

    return -1

print(ucs())