提高】卫星照片 USACO 显示标签 时间限制：C/C++ 1000MS，其他语言 2000MS 内存限制：C/C++ 128MB，其他语言 256MB 难度：普及 分数：100 OI排行榜得分：16(0.1*分数+2*难度) 出题人： 描述 农夫约翰总是想要一个农场的地图，所以他拍摄了一张N行M列的卫星照片。一部分的照片看起来像这样： .................. ..#####.......##.. ..#####......##... .................. #.......###.....#. #.....#####....... 他认为每个联通块都是一个谷仓或一头奶牛。联通块由若干个彼此水平或垂直相邻的＃符号组成。以下的照片被认为是两个联通块： .... .#.. ..#. .... 农夫约翰认为一个联通块是谷仓，当且仅当它是一个完整的矩形，否则该联通块是一头奶牛。在第一张照片上面，有三个谷仓（大小分别为2x1,2x5和1x1）和两头奶牛。 计算他的卫星照片中谷仓和奶牛的数量。 输入描述 行1：两个空格分隔的整数：N和M(N,M<=80)。

以下是使用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)$，主要用于存储访问标记数组。 [2026-02-03 17:15:10 | AI问答 | 850点数解答]