Foobar挑战“解救兔子逃生”代码本地正常但平台验证失败求助

问题背景 #

我正在解决Google Foobar第三关的「Prepare the Bunnies Escape」问题，代码在本地解释器运行能得到预期输出，但提交到Foobar平台后无法通过所有测试用例验证。

问题描述 #

拥有空间站部分区域地图，起点为左上角(0,0)，终点为右下角(w-1,h-1)。地图由0和1组成的矩阵表示：0是可通行区域，1是不可通行墙壁。允许拆除一面墙壁，求从起点到终点的最短路径长度（路径长度为经过的节点总数，包含起点和终点）。起点和终点始终可通行，地图一定可解，仅允许上下左右四个方向移动，不可斜向移动。

我的代码 #

class state:   
    
    def __init__(self,x,y,last_move,wall,path,map) -> None:
        self.x = x 
        self.y = y

        self.last_move = last_move   # Prevent Backtracking
        self.wall = wall
        self.path = path


    # MAP[x][y] = 1 => WALL
    # WALL = TRUE IF ALREADY ENCOUNTERED WALL
    def can_pass(self,map):
        global wall
        result = not(self.wall and map[self.x][self.y]) # NAND Function
        return result
    
    def new_wall(self,map):
        return self.wall or map[self.x][self.y]


    def create_children_states(self,map):
        moves = ["RIGHT","UP","DOWN","LEFT"] 
#Avoid backtracking
        if self.last_move == "RIGHT":
            moves.remove("LEFT")
        elif self.last_move == "LEFT":
            moves.remove("RIGHT")
        elif self.last_move == "UP":
            moves.remove("DOWN")
        elif self.last_move == "DOWN":
            moves.remove("UP")
        
        self.children_states=[]
        for move in moves:
            if self.can_pass(map):
                if move == "RIGHT" and stays_inbounds(self.y+1,targetY):
                    self.children_states.append(state(self.x,self.y + 1,move,self.new_wall(map),self.path+1,map))   # X, Y+1
                elif move == "UP" and stays_inbounds(self.x-1,targetX):
                    self.children_states.append(state(self.x - 1,self.y,move,self.new_wall(map),self.path+1,map))   # X-1, Y
                elif move == "DOWN" and stays_inbounds(self.x+1,targetX):
                    self.children_states.append(state(self.x + 1,self.y,move,self.new_wall(map),self.path+1,map))   # X+1 , Y 

                elif move == "LEFT" and stays_inbounds(self.y-1,targetY):
                    self.children_states.append(state(self.x,self.y - 1,move,self.new_wall(map),self.path+1,map))  # X , Y-1

    
def stays_inbounds(x,target): # Doesn't leave map
    return x <= target and x >= 0


def solution(map):
    global targetX
    global targetY
    targetX = len(map) - 1
    targetY = len(map[0]) - 1

    queue = [state(0,0,'',False,1,map)]

    while len(queue) > 0: 
        curr_state = queue.pop(0)
        if curr_state.x == targetX and curr_state.y == targetY: # Solution Found
            return curr_state.path
        else:
            curr_state.create_children_states(map)
            for child in curr_state.children_states:
                queue.append(child)

测试用例（本地运行符合预期） #

• 输入：solution([[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]])
  预期输出：7
• 输入：solution([[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]])
  预期输出：11

问题排查与修复建议 #

1. 全局变量的隐患 #

代码中使用global wall、targetX、targetY全局变量，在Foobar平台多测试用例环境下，全局变量会保留上一次运行的状态，导致后续测试用例出错。比如wall变量未初始化就被声明为全局，可能引发未定义行为。

• 修复：移除所有全局变量，将targetX/targetY作为参数传递，或在state类中存储。

2. 通行判断逻辑错误 #

can_pass方法判断的是当前状态坐标的通行性，但创建子状态时，应该判断子节点坐标的通行性，而非当前节点。当前代码在循环移动方向时，先调用self.can_pass(map)（判断当前位置），完全不符合逻辑。

• 修复：先计算子节点的新坐标，再针对新坐标判断是否可通行（基于当前状态的wall标记：若未拆过墙，允许走一次墙壁）。

3. 回溯限制的缺陷 #

通过last_move禁止反方向移动的逻辑，会错过需要绕路的最优路径（比如先向右再向左回退绕开墙壁）。BFS应通过访问标记避免重复访问，而非禁止反方向移动。

• 修复：移除基于last_move的回溯限制，改用状态访问标记控制重复处理。

4. 状态重复访问问题 #

当前代码未记录已访问的状态，同一个(x,y)位置可能被多次加入队列（带不同的wall状态），导致队列膨胀、效率低下，甚至超时或出错。

• 修复：维护一个三维数组visited[x][y][2]，其中visited[x][y][0]表示未拆墙时是否访问过(x,y)，visited[x][y][1]表示已拆墙时是否访问过，加入队列前检查该状态是否已被访问，未访问则标记并加入队列。

内容的提问来源于stack exchange，提问作者Melek