CodinGame《骑士之影》：Python双向二分查找导航算法详解

import sys
import math

class Jumper:
    """
    负责蝙蝠侠在建筑物中导航的类，利用双向二分查找策略。
    """
    def __init__(self):
        """
        初始化Jumper对象，读取建筑尺寸、最大跳跃次数和蝙蝠侠起始位置。
        并设置初始的X轴和Y轴搜索范围。
        """
        # 读取建筑宽度W和高度H
        w, h = [int(i) for i in input().split()]

        # 初始化X轴和Y轴的搜索范围
        # x_min, x_max 分别代表当前X轴搜索范围的下界和上界
        # y_min, y_max 分别代表当前Y轴搜索范围的下界和上界
        self.x_min, self.x_max = 0, w - 1
        self.y_min, self.y_max = 0, h - 1

        # 读取最大跳跃次数 (在本方案中并非核心逻辑，但保留以符合原题设定)
        self.jumps = int(input())

        # 读取蝙蝠侠的起始位置
        self.current_position = [int(i) for i in input().split()]

    def jump(self, direction: str) -> tuple:
        """
        根据炸弹方向信息，更新搜索范围并计算下一个跳跃点。

        Args:
            direction (str): 炸弹相对于蝙蝠侠当前位置的方向（如 'U', 'DR', 'L' 等）。

        Returns:
            tuple: 下一个跳跃点的 (x, y) 坐标。
        """
        # 定义方向映射：将方向字符串转换为对X轴和Y轴范围更新的逻辑
        # (水平方向调整值, 垂直方向调整值)
        # -1: 目标在左/上，0: 目标在当前行/列，1: 目标在右/下
        dir_map = {'U': (0, -1), 'UR': (1, -1), 'UL': (-1, -1),
                   'D': (0, 1), 'DR': (1, 1), 'DL': (-1, 1),
                   'R': (1, 0), 'L': (-1, 0), '': (0, 0)} # '' 用于调试或特殊情况

        horiz_dir, vert_dir = dir_map[direction]

        # 获取当前蝙蝠侠的X和Y坐标
        current_x, current_y = self.current_position[0], self.current_position[1]

        # X轴二分查找步骤：根据水平方向更新x_min和x_max
        if horiz_dir > 0:  # 需要向右移动，炸弹在当前X坐标的右侧
            self.x_min = current_x + 1
        elif horiz_dir < 0:  # 需要向左移动，炸弹在当前X坐标的左侧
            self.x_max = current_x - 1
        else:  # 水平方向不变，炸弹在当前X坐标上
            self.x_min = current_x
            self.x_max = current_x

        # 计算下一个X坐标：新范围的中间值
        # 使用 //2 进行整数除法，确保坐标是整数
        next_x = (self.x_min + self.x_max) // 2

        # Y轴二分查找步骤：根据垂直方向更新y_min和y_max
        if vert_dir > 0:  # 需要向下移动，炸弹在当前Y坐标的下方
            self.y_min = current_y + 1
        elif vert_dir < 0:  # 需要向上移动，炸弹在当前Y坐标的上方
            self.y_max = current_y - 1
        else:  # 垂直方向不变，炸弹在当前Y坐标上
            self.y_min = current_y
            self.y_max = current_y

        # 计算下一个Y坐标：新范围的中间值
        next_y = (self.y_min + self.y_max) // 2

        # 更新蝙蝠侠的当前位置为新的跳跃点
        self.current_position = [next_x, next_y]

        # 返回新的跳跃点坐标
        return tuple(self.current_position)

# 主游戏循环
if __name__ == '__main__':
    # 初始化Jumper对象
    batman = Jumper()

    # 游戏主循环
    while True:
        # 读取炸弹方向信息
        bomb_dir = input()  

        # 调用jump方法，计算下一个跳跃点
        x, y = batman.jump(direction=bomb_dir)

        # 输出下一个跳跃点的坐标
        print(f'{x} {y}')