未知起点RobotStub迷宫：虚拟坐标、探索与回退

题意与假设

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

• 静态有限四邻接迷宫，移动可逆、方向一致，无传送/单向门；API方向0上1右2下3左。
• 本文成功后停在goal，失败回到起点；若调用要求成功也回原位，需要另保存/执行回退路径。

解题路线

1. 起点虚拟坐标(0,0)，只为识别重访，不需知道地图真实原点。每尝试新邻居先canMove，成功移动才标已访问并开新frame。
2. 每frame保存未尝试方向iterator与退回父点的反向dir。邻居探索结束立即move反向，使物理位置恢复父frame；栈不变量是机器人在栈顶坐标。
3. 已访问开放格不重复进入，四边探索后结束；图静态且坐标一致意味着全部可达格被访问。API本身失败/不可逆会破坏证明，需题目合同保证或错误处理。

手动走一遍

一条路走到死端，frame耗尽后移动反方向回父格，再尝试另一分支；不是仅弹栈而把机器人物理位置留在死端。起点已goal立即True不移动；封闭起点False。

Python 参考实现

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

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

def find_goal(robot):
    # Directions are 0 up, 1 right, 2 down, 3 left; inverse=(d+2)%4.
    moves=((-1,0),(0,1),(1,0),(0,-1))
    seen={(0,0)};stack=[((0,0),iter(range(4)),None)]
    if robot.isGoal():return True
    while stack:
        (r,c),directions,back=stack[-1]
        d=next(directions,None)
        if d is None:
            stack.pop()
            if back is not None:robot.move(back)
            continue
        dr,dc=moves[d];v=(r+dr,c+dc)
        if v not in seen and robot.canMove(d):
            robot.move(d);seen.add(v)
            if robot.isGoal():return True
            stack.append((v,iter(range(4)),(d+2)%4))
    return False

复杂度

R可达开放格、E≤4R，O(R+E)API尝试/移动，O(R)seen/显式栈；DFS不保证最短路线。

易错点与追问

容易失分的边界

• 不能DFS虚拟坐标而不实际move回退。
• 如果存在同位置多状态（钥匙/门），visited仅坐标可能误剪。

继续深挖

• 要找最短路径，先探索建图再BFS，怎样将机器人从当前位置导航过去？
• API成本高时如何减少重复canMove与跨分支移动？