Python网格最优箭头位置求解：连续多目标计数问题求助

问题描述 #

• 给定n×n网格（边界为空单元格）及目标位置，需编写程序遍历所有边界单元格，找到放置箭头的最佳位置，使其在不遇到空单元格的情况下击中最多连续目标。
• 箭头方向定义：A=左，B=上，C=右，D=下，E=右上对角线，F=左上对角线，G=右下对角线，H=左下对角线。
• 输出为3字符字符串，格式为「位置+方向」，网格左上角为行0列0（行优先顺序）。
• 需实现函数FindArrowAI，参数为：grid_size（网格边长，如2代表2×2）、targets（目标位置字符串，每个位置为2字符，空格分隔）。函数返回符合要求的3字符字符串，若有多个结果，返回ASCII码顺序最靠前的字符串。

约束条件 #

• 输入的grid_size不超过10，所有目标位置均在网格内且不在边界单元格。
• 注：本题中X轴与Y轴是翻转的。

现有代码问题 #

当前代码仅能识别可击中2个目标的箭头位置，无法统计击中3个或更多目标的情况。以测试用例FindArrowAI(5, "31 21 13 32 11 12")为例，预期输出为"01D"，需完善代码实现统计最多连续目标的功能。

现有代码 #

## FUNCTION INPUT ##

def FindArrowAI(grid_size, targets):
    
    target_list = []
    target_lis = targets.split()

    arrow_list = []
    
    for z in target_lis:
        target_list.append(str(z))

    block_list = []

    count = 0

    size = [[0] * grid_size for _ in range(grid_size)]
    border_cells = []

    # Iterate over the cells in the size
    for i in range(grid_size):
        for j in range(grid_size):
            # Check if the current cell is on the border
            if i == 0 or i == grid_size - 1 or j == 0 or j == grid_size - 1:
                cell_coords = str(i) + str(j)  # Convert indices to strings and concatenate them
                border_cells.append(cell_coords)

    ## BLOCK IDENTIFICATION ##
    
    for block_y in range(0, grid_size, 1):
        for block_x in range(0, grid_size, 1):
            block_list.append(str(block_y) + str(block_x))
    for x in target_list:
        block_list.remove(x)


    ## TARGET IDENTIFICATION ##
    for i in target_list:
        if str(int(i[0]) + 0) + str(int(i[1]) - 1) in target_list:
            loc_a = str(int(i[0]) + 0) + str(int(i[1]) + 1)
            if loc_a in border_cells:
                arrow_list.append(str(loc_a) + "A")
                
    for i in target_list:
        if str(int(i[0]) - 1) + str(int(i[1]) + 0) in target_list:
            loc_b = str(int(i[0]) + 1) + str(int(i[1]) + 0)
            if loc_b in border_cells:
                arrow_list.append(str(loc_b) + "B")
            
    for i in target_list:
        if str(int(i[0]) + 0) + str(int(i[1]) + 1) in target_list:
            loc_c = str(int(i[0]) + 0) + str(int(i[1]) - 1)
            if loc_c in border_cells:
                arrow_list.append(str(loc_c) + "C")

    for i in target_list:
        if str(int(i[0]) + 1) + str(int(i[1]) + 0) in target_list:
            loc_d = str(int(i[0]) - 1) + str(int(i[1]) + 0)
            if loc_d in border_cells:
                arrow_list.append(str(loc_d) + "D")

    for i in target_list:
        if str(int(i[0]) - 1) + str(int(i[1]) - 1) in target_list:
            loc_e = str(int(i[0]) + 1) + str(int(i[1]) + 1)
            if loc_e in border_cells:
                arrow_list.append(str(loc_e) + "E")

    for i in target_list:
        if str(int(i[0]) - 1) + str(int(i[1]) + 1) in target_list:
            loc_f = str(int(i[0]) + 1) + str(int(i[1]) -1)
            if loc_f in border_cells:
                arrow_list.append(str(loc_f) + "F")
            
    for i in target_list:
        if str(int(i[0]) + 1) + str(int(i[1]) + 1) in target_list:
            loc_g = str(int(i[0]) - 1) + str(int(i[1]) - 1)
            if loc_g in border_cells:
                arrow_list.append(str(loc_g) + "G")

    for i in target_list:
        if str(int(i[0]) + 1) + str(int(i[1]) - 1) in target_list:
            loc_h = str(int(i[0]) - 1) + str(int(i[1]) + 1)
            if loc_h in border_cells:
                arrow_list.append(str(loc_h) + "H")
    print(arrow_list)
    print(target_list)
  
FindArrowAI(5, "31 21 13 32 11 12")

解决方案 #

核心思路是对每个边界位置的每个方向，模拟箭头发射路径，统计连续击中的目标数量（路径中不能出现空单元格），最终筛选出最优结果。

修正后的代码 #

def FindArrowAI(grid_size, targets):
    # 将目标位置转为集合，提升查询效率
    target_set = set(targets.split())
    # 定义8个方向对应的坐标偏移与方向字符
    directions = [
        (0, -1, 'A'),  # 左
        (-1, 0, 'B'),  # 上
        (0, 1, 'C'),   # 右
        (1, 0, 'D'),   # 下
        (-1, 1, 'E'),  # 右上对角线
        (-1, -1, 'F'), # 左上对角线
        (1, 1, 'G'),   # 右下对角线
        (1, -1, 'H')   # 左下对角线
    ]
    
    max_count = -1
    best_candidate = ""
    
    # 遍历所有边界单元格
    for row in range(grid_size):
        for col in range(grid_size):
            # 跳过非边界单元格
            if row != 0 and row != grid_size-1 and col !=0 and col != grid_size-1:
                continue
            current_pos = f"{row}{col}"
            
            # 尝试每个方向
            for dr, dc, dir_char in directions:
                count = 0
                r, c = row + dr, col + dc
                # 沿方向移动，直到超出网格或遇到非目标单元格
                while 0 <= r < grid_size and 0 <= c < grid_size:
                    pos = f"{r}{c}"
                    if pos in target_set:
                        count += 1
                        r += dr
                        c += dc
                    else:
                        # 遇到空单元格，停止统计
                        break
                # 更新最优结果
                if count > max_count:
                    max_count = count
                    best_candidate = current_pos + dir_char
                elif count == max_count:
                    # 数量相同时，选择ASCII顺序更靠前的字符串
                    if (current_pos + dir_char) < best_candidate:
                        best_candidate = current_pos + dir_char
    
    return best_candidate

# 测试用例验证
print(FindArrowAI(5, "31 21 13 32 11 12"))  # 输出: 01D

代码说明 #

• 目标集合：用set存储目标位置，查询时间复杂度为O(1)，提升统计效率。
• 方向统一管理：将每个方向的偏移量和对应字符整合为列表，避免重复代码。
• 路径模拟：对每个边界位置的每个方向，逐步移动并统计连续目标数，遇到非目标单元格立即终止。
• 最优筛选：记录最大击中数，若存在多个候选结果，通过字符串比较选择ASCII顺序最靠前的组合。

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