本文共 2323 字,大约阅读时间需要 7 分钟。
为了解决这个问题,我们需要找到一个冰激凌球,它的面积最大,并且在面积相同的情况下,周长最小。冰激凌球是一个连通的区域,其中每个冰激凌块都可以通过上下左右移动到其他冰激凌块。
import sysfrom collections import dequedef main(): n = int(sys.stdin.readline()) grid = [] for _ in range(n): line = sys.stdin.readline().strip() row = [1 if c == '#' else 0 for c in line] grid.append(row) visited = [[False for _ in range(n)] for __ in range(n)] neighbor_visited = [[False for _ in range(n)] for __ in range(n)] max_area = 0 min_perimeter = float('inf') for i in range(n): for j in range(n): if grid[i][j] == 1 and not visited[i][j]: queue = deque() queue.append((i, j)) visited[i][j] = True area = 1 perimeter = 0 while queue: x, y = queue.popleft() for k in range(4): dx = [0, 0, 0, 1] dy = [1, -1, 0, 0] nx = x + dx[k] ny = y + dy[k] if 0 <= nx < n and 0 <= ny < n: if grid[nx][ny] == 0 or (nx == 0 or nx == n-1 or ny == 0 or ny == n-1): if not neighbor_visited[nx][ny]: perimeter += 1 neighbor_visited[nx][ny] = True queue.append((nx, ny)) visited[nx][ny] = True if area > max_area: max_area = area min_perimeter = perimeter elif area == max_area and perimeter < min_perimeter: min_perimeter = perimeter print(max_area, min_perimeter)if __name__ == "__main__": main()
grid
来表示冰激凌块的位置。visited
数组记录哪些格子已经被访问过,neighbor_visited
数组记录哪些邻居已经被处理过。这个方法确保了我们能够高效地找到最大的冰激凌球,并计算其周长,满足题目要求。
转载地址:http://irpzz.baihongyu.com/