Meta 黑盒老鼠找奶酪：逻辑坐标与物理回退

题目重点：只能调用移动和当前位置检测接口，探索未知迷宫并保证失败时返回原位。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

训练move(direction)返回bool，失败不改位置，is_cheese检测当前格；静态有限4邻接迷宫，成功移动可用反方向回退。
成功停在奶酪，失败恢复起点；逻辑坐标从(0,0)任意定义，不读黑盒grid/绝对坐标。只有canMove而缺目标检测的接口不能直接套用。

解题路线

DFS栈记录逻辑位置、下一方向和返回父格的方向，seen按可达坐标避免环。坐标是相对移动累积，不需要知道矩形大小或障碍地图。
每个未访问邻居实际move，失败继续其他方向；成功登记seen、检查奶酪，未命中入栈探索。若子节点全部方向结束，用back方向真实移回父格，再继续父栈。
重要不变量：栈顶逻辑位置对应黑盒实际当前位置。仅pop逻辑栈而不move回去会让后续move相对错误格执行，seen坐标逐步失真。
命中立即返回，不继续回退，否则bool虽True机器却离开目标；失败时全部stack退完，所有成功探索边都逆向走回，因此实际位置回到起点。
本例迭代避免深走廊递归上限；失败回退如果move意外失败，说明静态可逆前提被破坏，抛异常不能继续假装位置一致。

手动走一遍

起点右边一条死路、下方通奶酪。探索右路结束必须left实际回到起点，才能down沿真正下路；只把逻辑coord设0,0不移动会从死路向下搜索错误位置。起点即奶酪可0移动成功。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

DIRECTIONS=(('up',-1,0,'down'),('right',0,1,'left'),('down',1,0,'up'),('left',0,-1,'right'))


def find_cheese(mouse):
    """Only move(direction)->bool and is_cheese()->bool. Static finite 4-grid.

    Failed move leaves position unchanged; reverse of successful move works.
    Success stops at cheese; failure restores starting position.
    """
    seen={(0,0)};stack=[(0,0,0,None)]
    if mouse.is_cheese():return True
    while stack:
        r,c,index,reverse=stack[-1]
        if index==4:
            stack.pop()
            if reverse is not None and not mouse.move(reverse):raise RuntimeError('maze changed during backtracking')
            continue
        stack[-1]=(r,c,index+1,reverse);direction,dr,dc,back=DIRECTIONS[index];next=(r+dr,c+dc)
        if next in seen:continue
        if not mouse.move(direction):continue
        seen.add(next)
        if mouse.is_cheese():return True
        stack.append((*next,0,back))
    return False

复杂度

V可达格、E邻边，O(V+E)逻辑/移动工作，4网格E=O(V)，空间O(V)seen/stack；死墙可能从多个邻格尝试但度数常数，仍线性。不提供最短路径，只保证找到可达目标。

易错点与追问

容易失分的边界

物理位置没有与回溯同步。
成功后强制回起点，却接口要求机器停目标。
访问坐标缺seen导致环无限走。

继续深挖

想求最短距离，先完整探索建图再BFS可行，但是否还需把机器移到目标？输出与状态要分别定。
动态门、钥匙或单向移动可能破坏逆向回退，需更完整状态/可恢复接口。