求助：CodinGame《Shadow of the Knight -1》Python二分搜索实现

问题概述 #

正在学习面向对象编程，通过CodinGame的《Shadow of the Knight - 1》谜题做交互式练习时，卡在二分搜索的实现环节。谜题核心要求是：在以(0,0)为左上角的矩形网格建筑中，根据炸弹相对当前位置的方向提示（U、UR、R、DR、D、DL、L、UL），通过有限次数的跳跃定位炸弹位置。初始化输入包含建筑宽W、高H、最大跳跃次数N、起始坐标X0/Y0，每轮需输出下一跳的坐标。

原实现思路试图将坐标存入有序二维数组，通过二分搜索树分区定位，但存在两个关键问题：

• 现有二分搜索仅支持一维列表，无法处理二维坐标
• 网格未正确排序，导致程序超时无响应

现有代码问题 #

原代码存在逻辑缺失与错误，比如未正确调用初始化方法、跳跃逻辑未实现、二分搜索逻辑与谜题需求不匹配：

import sys
import math

class Jumper():

    def __init__(self):
        self.grid = []
        self.jumps = 0
        self.current_position = (0, 0)

    def create_grid(self):
        w, h = [int(i) for i in input().split()]
        self.grid = [[0 for _ in range(w)] for _ in range(h)]
        self.jumps = int(input())  # maximum number of turns before game over.
        x0, y0 = [int(i) for i in input().split()]
        self.current_position = (x0, y0)

    def search(self, L, e):
        """Assumes L is a list, the elements of which are in ascending order. 
        Returns True if e is in L and False otherwise."""
        
        def binary_search(L, e, low, high):
            if high == low:
                return L[low] == e
            mid = (low+high)//2
            if L[mid] == e:
                return True
            elif L[mid] > e:
                if low == mid:
                    return False
                else:
                    return binary_search(L,e,low,mid-1)
            else:
                return binary_search(L,e,mid+1,high) 
        
        if not L:
            return False
        else:
            return binary_search(L,e,0,len(L)-1)
    
    def jump_to_position(self):
        while True:
            bomb_dir = input()  # the direction of the bombs from batman's current location (U, UR, R, DR, D, DL, L or UL)
            # the location of the next window Batman should jump to.
            print("0 0")


batman = Jumper()
batman.read_inputs()
batman.search()

优化方案与修正代码 #

无需存储整个网格，只需维护当前搜索的边界范围，对X、Y维度分别做二分收缩即可，这是最适配谜题需求的高效实现方式：

import sys
import math

class Jumper():

    def __init__(self):
        self.jumps = 0
        self.current_position = (0, 0)
        # 维护当前搜索范围的边界
        self.x_min = 0
        self.x_max = 0
        self.y_min = 0
        self.y_max = 0

    def init_search_range(self):
        w, h = [int(i) for i in input().split()]
        self.x_max = w - 1
        self.y_max = h - 1
        self.jumps = int(input())
        x0, y0 = [int(i) for i in input().split()]
        self.current_position = (x0, y0)

    def jump_to_position(self):
        while True:
            bomb_dir = input().strip()
            curr_x, curr_y = self.current_position

            # 根据方向提示收缩搜索边界
            if 'U' in bomb_dir:
                self.y_max = curr_y - 1
            elif 'D' in bomb_dir:
                self.y_min = curr_y + 1

            if 'L' in bomb_dir:
                self.x_max = curr_x - 1
            elif 'R' in bomb_dir:
                self.x_min = curr_x + 1

            # 计算当前范围的中点作为下一跳坐标（二分核心）
            new_x = (self.x_min + self.x_max) // 2
            new_y = (self.y_min + self.y_max) // 2
            self.current_position = (new_x, new_y)

            print(new_x, new_y)


batman = Jumper()
batman.init_search_range()
batman.jump_to_position()

优化说明 #

1. 移除冗余网格存储：仅通过四个边界变量维护当前可能的搜索范围，避免不必要的内存占用与数组操作
2. 简化二维二分逻辑：对X、Y维度独立做二分收缩，每次跳跃直接跳到当前范围中点，保证最优搜索效率，符合谜题的次数限制要求
3. 修复逻辑错误：修正原代码中方法调用错误、跳跃逻辑缺失等问题，确保程序能持续处理输入并输出正确坐标

修复后预期输出示例 #

Game information:
Locate the bombs, save the hostages!
Batman is on window (2,3)
The bombs are located below and to the right of Batman

5 5
Game information:
Batman is on window (5,5)
The bombs are located below and to the right of Batman

7 7
...

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