USACO：用Python代码解析卫星照片中谷仓与奶牛的数量

以下是使用Python语言解决此问题的代码： ```python # 定义深度优先搜索函数，用于标记和检查连通块 def dfs(x, y, visited, grid): rows, cols = len(grid), len(grid[0]) # 存储连通块中 # 字符的坐标 positions = [] stack = [(x, y)] while stack: cur_x, cur_y = stack.pop() # 如果越界、已经访问过或者不是 # 字符，跳过 if cur_x < 0 or cur_x >= rows or cur_y < 0 or cur_y >= cols or visited[cur_x][cur_y] or grid[cur_x][cur_y] != '#': continue # 标记为已访问 visited[cur_x][cur_y] = True positions.append((cur_x, cur_y)) # 向四个方向扩展 stack.append((cur_x + 1, cur_y)) stack.append((cur_x - 1, cur_y)) stack.append((cur_x, cur_y + 1)) stack.append((cur_x, cur_y - 1)) # 检查连通块是否为矩形 min_x = min([pos[0] for pos in positions]) max_x = max([pos[0] for pos in positions]) min_y = min([pos[1] for pos in positions]) max_y = max([pos[1] for pos in positions]) for i in range(min_x, max_x + 1): for j in range(min_y, max_y + 1): if grid[i][j] != '#': return False return True # 读取输入 n, m = map(int, input().split()) grid = [input() for _ in range(n)] # 初始化访问标记数组 visited = [[False] * m for _ in range(n)] barns = 0 cows = 0 # 遍历整个网格 for i in range(n): for j in range(m): if grid[i][j] == '#' and not visited[i][j]: if dfs(i, j, visited, grid): barns += 1 else: cows += 1 # 输出结果 print(barns) print(cows) ``` 代码解释： 1. `dfs` 函数：该函数使用深度优先搜索（DFS）来遍历连通块。它接受当前位置 `(x, y)`、访问标记数组 `visited` 和网格 `grid` 作为参数。在 DFS 过程中，将连通块中所有 `#` 字符的坐标存储在 `positions` 列表中。然后，通过计算这些坐标的最小和最大 `x`、`y` 坐标，检查该连通块是否为矩形。如果是矩形，则返回 `True`，否则返回 `False`。 2. 主程序：首先读取输入的行数 `n` 和列数 `m`，以及网格数据。然后初始化访问标记数组 `visited`，用于记录每个位置是否已经被访问过。接着，遍历整个网格，对于每个未访问过的 `#` 字符，调用 `dfs` 函数进行检查。如果返回 `True`，则该连通块是谷仓，`barns` 计数器加 1；否则，该连通块是奶牛，`cows` 计数器加 1。输出谷仓和奶牛的数量。 复杂度分析： - 时间复杂度：$O(N * M)$，其中 $N$ 是行数，$M$ 是列数。因为每个位置最多被访问一次。 - 空间复杂度：$O(N * M)$，主要用于存储访问标记数组。 ######[AI问答 | 850点数解答 | 2026-02-03 17:15:10]