油田计数与冰淇淋球面积周长计算
油田计数（Oil Deposits）
题目描述
GeoSurvComp 地质调查公司负责探测地下油田。现在需要你编写一个程序，来统计一块矩形区域内有多少个独立的油田。
规则说明
- 输入会给出一个由
@（代表油田）和*（代表空地）组成的二维网格；- 一个油田定义为：所有相邻的
@组成的集合（相邻包括上下左右四个方向，以及左上、右上、左下、右下四个对角线方向，共 8 个方向）；- 输入包含多组测试数据：
- 每组数据第一行是两个整数
n和m（分别表示网格的行数和列数）；- 接下来
n行，每行是长度为m的字符串（仅包含@和*）；- 当输入的
n和m均为 0 时，表示输入结束。- 对于每组测试数据，输出该网格中独立油田的数量。
def youtian(): while True: n, m = map(int, input().split()) if n == 0 and m == 0: break grid = [] for _ in range(n): # 注意：input().split() 会按空格拆分，若输入是连续字符（如@*@）需用list(input().strip()) grid.append(list(input().strip())) # 方向数组：8个方向（上下左右+四个对角线） dirs = [(1,0), (-1,0), (0,-1), (0,1), (1,1), (-1,-1), (1,-1), (-1,1)] count = 0 def dfs(x, y): # 将当前油田标记为已访问（用*替代） grid[x][y] = '*' for dx, dy in dirs: nx = x + dx ny = y + dy # 边界检查 + 检查是否是未访问的油田（@） if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == '@': dfs(nx, ny) # 遍历整个网格，统计油田数量 for i in range(n): for j in range(m): if grid[i][j] == '@': count += 1 dfs(i, j) print(count) if __name__ == "__main__": # 等号两侧加空格，符合PEP8规范 youtian()冰淇凌统计问题
- 所有冰淇淋球里，面积最大的那个的面积是多少？（面积就是这个球里
#的数量） - 如果有多个冰淇淋球的面积并列最大，他想知道其中周长最小的那个的周长是多少。
import sys sys.setrecursionlimit(1000000) # 递归深度设更大，适配N=1000的情况 def ice_cream_blocks(): # 输入网格大小（题目是N×N，这里兼容N×M） n = int(input()) # 若题目是N×M，改为 n, m = map(int, input().split()) m = n # 题目是N×N，所以m=n；如果是通用N×M，删掉这行 # 读取网格 grid = [list(input().strip()) for _ in range(n)] # 标记是否访问过（避免重复计算同一个冰淇淋球） visited = [[False for _ in range(m)] for _ in range(n)] # 四个移动方向（上下左右） dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)] max_area = 0 # 记录最大面积 min_peri = float('inf') # 记录最大面积对应的最小周长 def dfs(x, y): """DFS遍历单个冰淇淋球，返回面积和周长""" nonlocal current_area, current_peri # 统计当前冰淇淋球的面积（每访问一个#，面积+1） current_area += 1 # 遍历四个方向，计算周长+递归遍历相邻# for dx, dy in dirs: nx, ny = x + dx, y + dy # 情况1：超出网格边界 → 周长+1 if nx < 0 or nx >= n or ny < 0 or ny >= m: current_peri += 1 # 情况2：在网格内，但不是#（是.）→ 周长+1 elif grid[nx][ny] == '.': current_peri += 1 # 情况3：在网格内，是#且未访问 → 递归遍历 elif not visited[nx][ny] and grid[nx][ny] == '#': visited[nx][ny] = True dfs(nx, ny) # 遍历整个网格，找所有冰淇淋球 for i in range(n): for j in range(m): # 找到未访问的#，开始遍历一个新的冰淇淋球 if not visited[i][j] and grid[i][j] == '#': visited[i][j] = True current_area = 0 # 当前球的面积 current_peri = 0 # 当前球的周长 dfs(i, j) # 遍历这个球的所有# # 更新最大面积和对应最小周长 if current_area > max_area: max_area = current_area min_peri = current_peri # 面积相等时，选周长更小的 elif current_area == max_area: if current_peri < min_peri: min_peri = current_peri # 输出结果（最大面积 + 对应最小周长） print(max_area, min_peri) if __name__ == "__main__": ice_cream_blocks()