USACO 2D网格奶牛交友最大对数Python代码超时优化求助

现有代码核心问题 #

1. 输入效率低：逐行调用input()处理大规模数据速度慢，Python中IO操作是常见的性能瓶颈。
2. 成员查询效率极低：用列表存储已配对奶牛对，(a,b) in friends是线性时间复杂度，当配对数量级达到1e5时会直接超时。
3. 边界判断笔误：原有代码边界判断写了j+k[0] > -1，应该是j + k[1] >=0，该bug会漏判大量合法相邻奶牛。
4. 逻辑冗余：不需要凑够2个C就立刻判断是否重复，应该先收集所有相邻C再统一处理，且配对存储时可以排序后存，避免同时校验(a,b)和(b,a)两种情况。

优化思路 #

1. 输入优化：用sys.stdin.read()一次性读取所有输入内容，比逐行读快数倍。
2. 去重优化：给每个奶牛分配唯一整数ID（坐标(i,j)对应i*m +j），配对存储时用(min(id1,id2), max(id1,id2))作为唯一标识，存入哈希集合，查询复杂度O(1)。
3. 匹配逻辑优化：
   • 优先处理周围恰好有2个C的G：这类G只能服务这一对奶牛，优先匹配不会影响全局最优解。
   • 后处理周围有>=3个C的G：随便选两个未配对的C匹配即可，不会抢占只能用特定G的配对资源。

优化后代码 #

import sys

def main():
    data = sys.stdin.read().split()
    ptr = 0
    n = int(data[ptr])
    ptr += 1
    m = int(data[ptr])
    ptr += 1
    grid = []
    for _ in range(n):
        grid.append(data[ptr])
        ptr += 1
    
    dirs = [(-1,0), (1,0), (0,-1), (0,1)]
    used_pairs = set()
    res = 0
    multi_g = []

    # 先处理只能服务一对奶牛的G
    for i in range(n):
        for j in range(m):
            if grid[i][j] != 'G':
                continue
            cs = []
            for dx, dy in dirs:
                nx = i + dx
                ny = j + dy
                if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 'C':
                    cs.append(nx * m + ny)
                    if len(cs) > 2:
                        break
            if len(cs) < 2:
                continue
            if len(cs) == 2:
                a, b = sorted(cs)
                if (a, b) not in used_pairs:
                    used_pairs.add((a, b))
                    res += 1
            else:
                multi_g.append(cs)
    
    # 再处理能服务多对奶牛的G
    for cs in multi_g:
        found = False
        for i in range(len(cs)):
            for j in range(i+1, len(cs)):
                a, b = sorted((cs[i], cs[j]))
                if (a, b) not in used_pairs:
                    used_pairs.add((a, b))
                    res += 1
                    found = True
                    break
            if found:
                break
    print(res)

if __name__ == "__main__":
    main()

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