油田计数与冰淇淋球面积周长计算

油田计数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) # 递归深度设更大适配N1000的情况 def ice_cream_blocks(): # 输入网格大小题目是N×N这里兼容N×M n int(input()) # 若题目是N×M改为 n, m map(int, input().split()) m n # 题目是N×N所以mn如果是通用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()