Python代码解决Kattis 10kindsofpeople问题遇运行时错误求助

看起来你遇到的运行时错误大概率是递归栈溢出导致的，咱们来一步步拆解问题，找到修复方案：

核心问题：递归DFS的深度限制 #

你的walk函数用了递归实现深度优先搜索（DFS），但Python默认的递归调用深度上限是1000左右。当测试用例是超大网格（比如1000x1000），或者需要遍历的路径特别长时，递归调用层数会超过这个限制，直接触发RecursionError——这应该就是第23个测试用例失败的原因。

除此之外，你的代码还有两个可以优化的点：

• 用字符串"{0},{1}".format(r1,c1)作为字典键，比直接用元组(r1,c1)慢不少，还会额外占用内存；
• 每次查询都重新跑一遍DFS，完全没有复用之前的计算结果，遇到大量查询的测试用例时，效率会极低，甚至可能超时。

修复方案：两种思路解决问题 #

思路1：把递归DFS改成迭代版本（快速修复） #

用栈来模拟递归过程，彻底避开递归深度限制的问题，代码改动不大：

def walk(arr, r1, c1, r2, c2, rows, cols):
    # 先判断起点终点数值是否一致，不一致直接返回False
    if arr[r1][c1] != arr[r2][c2]:
        return False
    # 起点就是终点，直接返回True
    if r1 == r2 and c1 == c2:
        return True
    
    visited = set()
    stack = [(r1, c1)]
    visited.add((r1, c1))
    # 上下左右四个方向
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while stack:
        current_r, current_c = stack.pop()
        for dr, dc in directions:
            new_r = current_r + dr
            new_c = current_c + dc
            # 检查新坐标是否在网格范围内
            if 0 <= new_r < rows and 0 <= new_c < cols:
                # 找到终点了
                if new_r == r2 and new_c == c2:
                    return True
                # 如果没访问过，且数值和起点一致，加入栈继续遍历
                if (new_r, new_c) not in visited and arr[new_r][new_c] == arr[r1][c1]:
                    visited.add((new_r, new_c))
                    stack.append((new_r, new_c))
    # 遍历完所有可达点都没找到终点
    return False

思路2：预处理连通分量（更高效，适合多查询场景） #

因为题目会有多个查询请求，我们可以提前给每个格子标记所属的连通区域ID——同一个连通区域内的格子，数值相同且互相可达。之后查询时，只需要判断两个点是否同属一个连通区域即可，查询时间直接降到O(1)：

if __name__ == "__main__":
    # 读取网格尺寸
    rows, cols = map(int, input().split())
    # 读取网格数据
    grid = []
    for _ in range(rows):
        grid.append([int(char) for char in input().strip()])
    
    # 预处理连通分量：给每个格子分配区域ID
    visited = [[False for _ in range(cols)] for _ in range(rows)]
    component_id = [[0 for _ in range(cols)] for _ in range(rows)]
    current_id = 0
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    for r in range(rows):
        for c in range(cols):
            if not visited[r][c]:
                current_id += 1
                # 用栈做迭代DFS遍历整个连通区域
                stack = [(r, c)]
                visited[r][c] = True
                component_id[r][c] = current_id
                current_val = grid[r][c]
                
                while stack:
                    cr, cc = stack.pop()
                    for dr, dc in directions:
                        nr = cr + dr
                        nc = cc + dc
                        if 0 <= nr < rows and 0 <= nc < cols:
                            if not visited[nr][nc] and grid[nr][nc] == current_val:
                                visited[nr][nc] = True
                                component_id[nr][nc] = current_id
                                stack.append((nr, nc))
    
    # 处理所有查询
    query_count = int(input())
    for _ in range(query_count):
        r1, c1, r2, c2 = map(int, input().split())
        # 转换成0索引
        r1 -= 1
        c1 -= 1
        r2 -= 1
        c2 -= 1
        
        if grid[r1][c1] != grid[r2][c2]:
            print("neither")
        elif component_id[r1][c1] == component_id[r2][c2]:
            print("binary" if grid[r1][c1] == 0 else "decimal")
        else:
            print("neither")

额外的小优化建议 #

• 输入处理时，用map(int, input().split())直接转换数值，比先存字符串再逐个处理更简洁高效；
• 用集合set或者二维数组存储已访问状态，比字符串键的字典性能更好；
• 预处理连通分量的方式在查询量很大时优势非常明显，能避免重复计算。

为什么第23个测试用例会报错？ #

第23个测试用例应该是一个超大网格+长路径的场景，你的递归DFS调用层数超过了Python默认的递归深度上限（默认是1000），导致抛出RecursionError。改用迭代DFS或者预处理连通分量就能完美解决这个问题。

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