求解2D迷宫：如何规避隐藏测试用例引发的运行时错误？

核心错误点 #

1. 行列变量搞反，导致矩阵读取错误
   输入格式是每组先输入行数r和列数c，但代码中错误地将width, height = map(int, input().split())，随后用for i in range(width)读取行，这会导致当r≠c时，读取的行数与实际要求不符（比如r=5、c=3时，仅读取3行而非5行），后续访问矩阵时必然触发索引越界。

2. 坐标顺序颠倒，引发BFS访问错误

   • find函数返回的是(行索引i, 列索引j)，但BFS中把该元组当作(x,y)（x为列索引、y为行索引），导致maze[y][x]实际访问的是maze[j][i]，完全颠倒了行列关系，要么触发索引越界，要么导致路径搜索逻辑错误。
   • BFS的边界判断0 <= x2 < width and 0 <= y2 < height中，x对应列、y对应行，因此起点坐标应是(j,i)而非(i,j)。

3. 未处理起点/终点缺失的极端情况
   如果测试用例中没有'D'或'S'，find函数会返回None，后续执行start[0]会直接抛出TypeError。

4. 递归转换矩阵效率低下且不必要
   change函数用递归处理二维矩阵，对于简单的列表嵌套完全没必要，还可能带来额外的栈开销。

修复后的代码 #

import collections

def bfs(maze, start, width, height, goal_val):
    queue = collections.deque()
    queue.append(start)
    seen = set([start])
    while queue:
        x, y = queue.popleft()  # x为列索引，y为行索引
        if maze[y][x] == goal_val:
            return True
        # 遍历上下左右四个方向
        for dx, dy in ((1,0), (-1,0), (0,1), (0,-1)):
            nx = x + dx
            ny = y + dy
            if 0 <= nx < width and 0 <= ny < height:
                if maze[ny][nx] != 1 and (nx, ny) not in seen:
                    queue.append((nx, ny))
                    seen.add((nx, ny))
    return False

def find_target(matrix, target):
    for y in range(len(matrix)):
        for x in range(len(matrix[y])):
            if matrix[y][x] == target:
                return (x, y)  # 返回符合BFS逻辑的(列索引, 行索引)
    return None

n = int(input())
for _ in range(n):
    # 读取行数和列数，对应矩阵的行、列
    rows, cols = map(int, input().split())
    mat = []
    for _ in range(rows):
        line = input().strip()
        mat.append(list(line))
    
    # 转换矩阵：可走区域转0，不可走转1，终点S转特殊值-1
    goal_val = -1
    for y in range(rows):
        for x in range(cols):
            char = mat[y][x]
            if char in ('.', 'o', 'D'):
                mat[y][x] = 0
            elif char in ('W', 'M', 'T'):
                mat[y][x] = 1
            elif char == 'S':
                mat[y][x] = goal_val
    
    # 查找起点（D已转为0）和终点
    start = find_target(mat, 0)
    end = find_target(mat, goal_val)
    
    # 处理起点/终点不存在的情况
    if not start or not end:
        print("Silence is a friend that never betrays")
        continue
    
    # 执行BFS并输出结果
    if bfs(mat, start, cols, rows, goal_val):
        print("We Making Waffles!!")
    else:
        print("Silence is a friend that never betrays")

修复说明 #

• 修正行列逻辑：用rows和cols对应输入的行数和列数，确保读取的行数与输入要求一致。
• 统一坐标规则：find_target直接返回BFS需要的(列索引x, 行索引y)，保证矩阵访问的正确性。
• 处理边界异常：增加对起点/终点不存在的判断，避免None引发的类型错误。
• 简化矩阵转换：用双重循环替代递归，直接完成字符到数值的转换，用特殊值标记终点避免混淆。
• 优化BFS逻辑：用方向向量(dx, dy)简化方向遍历，边界判断和访问逻辑更直观。

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