如何以最少步数在W×H矩阵中定位未知目标？

问题背景 #

现有一个W×H的矩阵，起始位置为随机坐标(x0,y0)，目标坐标未知。每一步可获取目标的8个方向信息（U、UR、R、DR、D、DL、L、UL），移动后需继续根据新方向缩小范围，核心目标是用最少步数找到目标。

当前实现思路是维护两个列表分别记录可能的X、Y坐标范围，每一步根据方向剔除不可能的坐标，然后移动到剩余区间的中点。想问有没有步数更少的实现方法？

当前实现代码（修复bug+中文注释版） #

原代码存在遍历过程中修改列表导致的索引异常问题，以下是修复后的版本：

w, h = [int(i) for i in input().split()]
n = int(input())  # 游戏结束前的最大步数限制
x0, y0 = [int(i) for i in input().split()]
currentx = x0
currenty = y0
xes = [i for i in range(w)]  # 记录可能的X坐标集合
yes = [i for i in range(h)]  # 记录可能的Y坐标集合

while True:
    bomb_dir = input() # 获取目标方向：U、UR、R、DR、D、DL、L 或 UL
    
    # 根据方向过滤X坐标（遍历副本避免修改原列表导致的遍历异常）
    if 'R' in bomb_dir:
        xes = [x for x in xes if x > currentx]
    elif 'L' in bomb_dir:
        xes = [x for x in xes if x < currentx]
    
    # 根据方向过滤Y坐标
    if 'U' in bomb_dir:
        yes = [y for y in yes if y < currenty]
    elif 'D' in bomb_dir:
        yes = [y for y in yes if y > currenty]
    
    # 移动到剩余区间的中点
    currentx = xes[round(len(xes)/2)-1] if xes else currentx
    currenty = yes[round(len(yes)/2)-1] if yes else currenty
    print(currentx, currenty)

更优实现方法：区间边界收缩+二分法 #

当前方法用列表存储坐标集合，操作效率低且易出错，改用区间边界维护+二分法能大幅减少步数，这是理论上的最优策略：

优化核心思路 #

1. 用x_min、x_max替代X坐标列表，y_min、y_max替代Y坐标列表，直接维护可能的坐标区间，避免冗余的列表操作。
2. 每次根据方向信息精准收缩区间：
   • 收到R时，直接将X区间左边界更新为currentx + 1（目标在右侧）；
   • 收到UL时，同时将X区间右边界设为currentx - 1、Y区间左边界设为currenty + 1（目标在左上方）；
   • 其他方向同理，一次操作完成双轴区间收缩。
3. 移动位置选择区间中点，确保每次将剩余范围缩小一半，步数为对数级。

优化后代码 #

w, h = [int(i) for i in input().split()]
n = int(input())  # 最大步数限制
x0, y0 = [int(i) for i in input().split()]

# 初始化X、Y的可能区间边界
x_min, x_max = 0, w - 1
y_min, y_max = 0, h - 1
currentx, currenty = x0, y0

while True:
    bomb_dir = input()
    
    # 更新X区间
    if 'R' in bomb_dir:
        x_min = max(x_min, currentx + 1)
    if 'L' in bomb_dir:
        x_max = min(x_max, currentx - 1)
    
    # 更新Y区间
    if 'U' in bomb_dir:
        y_min = max(y_min, currenty + 1)
    if 'D' in bomb_dir:
        y_max = min(y_max, currenty - 1)
    
    # 计算新位置：区间中点，确保在有效范围内
    currentx = (x_min + x_max) // 2
    currenty = (y_min + y_max) // 2
    print(currentx, currenty)

为什么步数更少？ #

• 原方法用列表存储坐标，删除元素的操作不仅效率低，还可能因为逻辑漏洞导致范围收缩不彻底，浪费步数。
• 优化后的区间维护法，每次精准收缩边界，没有冗余操作，中点选择能保证剩余范围每次减半，步数为log2(W) + log2(H)级，是理论最优的搜索步数。
• 斜向方向（如UR）能同时触发双轴区间更新，一步完成两个维度的范围收缩，比原方法效率更高。

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