在互动式编程挑战中，尤其是在涉及网格导航的场景下，如何高效地定位目标位置是一个常见且关键的问题。CodinGame的《蝙蝠侠：骑士的阴影》谜题便是一个典型的例子：玩家需要在限定的跳跃次数内，根据炸弹相对于当前位置的方向提示（如“上”、“右下”等），在建筑物（一个2D窗口网格）中找到炸弹的精确坐标。传统的1D二分查找算法在此类2D动态场景中显得力不从心，需要一种更具适应性的策略。
1. 2D导航与二分查找的本质
二分查找的核心在于通过每次比较将搜索空间减半，从而以对数时间复杂度快速定位目标。然而，在2D网格中，我们没有一个单一的“有序列表”可供直接查找。本教程将介绍一种将2D导航问题转化为两个相互独立的1D二分查找的方法，即分别对X轴（宽度）和Y轴（高度）进行二分查找。
游戏的反馈机制是关键：它不直接提供目标坐标，而是给出炸弹相对于蝙蝠侠当前位置的方向。这些方向提示（U, D, L, R, UR, DR, UL, DL）本质上就是二分查找中的“目标比当前值大”、“目标比当前值小”或“目标就是当前值”的判断依据。
2. 核心思想：双轴独立二分查找
为了在2D网格中应用二分查找，我们维护两个独立的搜索范围：一个用于X轴（min_x, max_x），另一个用于Y轴（min_y, max_y）。
初始化搜索范围：在游戏开始时，X轴的搜索范围是 [0, 建筑物宽度-1]，Y轴的搜索范围是 [0, 建筑物高度-1]。蝙蝠侠的起始位置 (X0, Y0) 是第一次跳跃的起点。
-
解析方向反馈：每回合，游戏会提供一个方向字符串。我们需要解析这个字符串，以确定炸弹在水平方向（左/右）和垂直方向（上/下）上的位置。
- 如果方向包含 'R' (Right)，说明炸弹在当前X坐标的右侧，因此新的X轴最小边界应为 当前X坐标 + 1。
- 如果方向包含 'L' (Left)，说明炸弹在当前X坐标的左侧，因此新的X轴最大边界应为 当前X坐标 - 1。
- 如果方向不包含 'R' 也不包含 'L'（例如 'U' 或 'D'），则说明炸弹的X坐标与当前X坐标相同，此时X轴的搜索范围应被锁定为 [当前X坐标, 当前X坐标]。
- Y轴的更新逻辑与X轴类似，根据 'U' (Up) 和 'D' (Down) 进行调整。
计算下一次跳跃点：在更新了X轴和Y轴的搜索边界后，下一次跳跃的目标点就是这两个新边界各自的中间值。例如，新的X坐标将是 (min_x + max_x) // 2，新的Y坐标将是 (min_y + max_y) // 2。
更新当前位置：将蝙蝠侠的当前位置更新为计算出的下一次跳跃点，并重复上述过程，直到找到炸弹。
3. Python 实现示例
我们将通过一个 Jumper 类来封装游戏的逻辑和状态，使其更具模块化和可读性。
import sys
class Jumper:
"""
Jumper 类用于处理蝙蝠侠在2D建筑物中的导航逻辑。
它通过维护X和Y轴的搜索边界，并根据游戏的方向反馈来更新这些边界，
从而实现高效的二分查找式导航。
"""
def __init__(self):
"""
初始化Jumper对象，读取建筑物的尺寸、最大跳跃次数和蝙蝠侠的起始位置。
同时设置X和Y轴的初始搜索边界。
"""
# 读取建筑物宽度W和高度H
W, H = map(int, input().split())
# 读取最大跳跃次数N (在本解决方案中主要用于游戏逻辑，不直接影响搜索算法)
self.max_jumps = int(input())
# 读取蝙蝠侠的起始坐标X0, Y0
X0, Y0 = map(int, input().split())
# 初始化X轴的搜索边界 [min_x, max_x]
self.min_x, self.max_x = 0, W - 1
# 初始化Y轴的搜索边界 [min_y, max_y]
self.min_y, self.max_y = 0, H - 1
# 设置蝙蝠侠的当前位置
self.current_x, self.current_y = X0, Y0
def jump(self, direction: str) -> tuple[int, int]:
"""
根据炸弹的方向反馈更新搜索边界，并计算下一次跳跃的目标位置。
Args:
direction (str): 炸弹相对于蝙蝠侠当前位置的方向字符串
(U, UR, R, DR, D, DL, L, UL)。
Returns:
tuple[int, int]: 下一次跳跃的X和Y坐标。
"""
# 根据水平方向（R/L）更新X轴边界
if 'R' in direction: # 炸弹在当前X坐标的右侧
self.min_x = self.current_x + 1
elif 'L' in direction: # 炸弹在当前X坐标的左侧
self.max_x = self.current_x - 1
else: # 方向中不包含'R'或'L'，表示炸弹在当前X列，X坐标已确定
self.min_x = self.current_x
self.max_x = self.current_x
# 根据垂直方向（U/D）更新Y轴边界
if 'D' in direction: # 炸弹在当前Y坐标的下方
self.min_y = self.current_y + 1
elif 'U' in direction: # 炸弹在当前Y坐标的上方
self.max_y = self.current_y - 1
else: # 方向中不包含'U'或'D'，表示炸弹在当前Y行，Y坐标已确定
self.min_y = self.current_y
self.max_y = self.current_y
# 计算下一次跳跃的目标位置（取当前有效搜索范围的中间点）
next_x = (self.min_x + self.max_x) // 2
next_y = (self.min_y + self.max_y) // 2
# 更新蝙蝠侠的当前位置为新的跳跃点，为下一回合做准备
self.current_x, self.current_y = next_x, next_y
# 返回计算出的新坐标
return self.current_x, self.current_y
# 主游戏循环
if __name__ == "__main__":
# 初始化Jumper对象，读取游戏初始参数
batman = Jumper()
# 进入无限循环，模拟游戏回合
while True:
# 读取炸弹的方向反馈
bomb_dir = input() # 例如: "U", "UR", "R", "DR", "D", "DL", "L", "UL"
# 调用jump方法计算下一次跳跃的坐标
x, y = batman.jump(direction=bomb_dir)
# 输出下一次跳跃的坐标，格式为 "X Y"
print(f'{x} {y}')
4. 注意事项与总结
- 边界处理的精确性：在更新 min_x/y 和 max_x/y 时，务必确保 +1 和 -1 的逻辑正确。例如，如果炸弹在右侧，那么当前位置 current_x 本身就不是目标，所以新的最小X坐标应从 current_x + 1 开始。
- 整数除法：Python 的 // 运算符执行整数除法，这对于计算中间点非常重要，因为它会自动向下取整。
- 游戏循环集成：此方案将二分查找的迭代逻辑融入到游戏的 while 循环中，每次循环处理一回合的输入和输出。这与传统的递归式二分查找不同，更适应交互式编程挑战的需求。
- 效率：由于每次跳跃都将X和Y的搜索空间减半，该算法的时间复杂度为 O(log W + log H)，即 O(log(W*H))，在大型网格中表现出极高的效率。
- 适用性：这种将2D问题分解为两个1D二分查找的策略，不仅适用于本例中的游戏，也广泛应用于其他需要根据方向或比较结果在2D空间中定位目标的场景。
通过上述方法，我们成功地将一个看似复杂的2D导航问题，巧妙地转化并解决了。关键在于理解二分查找的本质——缩小搜索空间，并将其应用于每个独立的维度，同时利用游戏提供的方向反馈作为决策依据。
