本文共 2845 字，大约阅读时间需要 9 分钟。
为了解决这个问题，我们需要找到一个 2D 格子中最大的轴对齐正号的大小 k。正号的中心必须是 1，并且从中心向四个方向（上、下、左、右）延伸的每个方向上都必须有连续的 1。
问题分析:
辅助矩阵:
left, right, up, down 分别记录从每个格子出发向左、右、上、下延伸的最大步数。计算最大正号:
def order_of_largest_plus_sign(): import sys input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 mines = [] for _ in range(int(input[ptr])): i = int(input[ptr]) j = int(input[ptr+1]) mines.append((i, j)) ptr += 2 # 初始化 grid grid = [[N for _ in range(N)] for __ in range(N)] for i, j in mines: grid[i][j] = 0 # 初始化辅助矩阵 left = [[0]*N for _ in range(N)] right = [[0]*N for _ in range(N)] up = [[0]*N for _ in range(N)] down = [[0]*N for _ in range(N)] # 填充 left 矩阵 for i in range(N): for j in range(N): if j == 0: if grid[i][j] != 0: left[i][j] = 1 else: left[i][j] = 0 else: if grid[i][j] != 0: left[i][j] = left[i][j-1] + 1 else: left[i][j] = 0 # 填充 right 矩阵 for i in range(N): for j in reversed(range(N)): if j == N-1: if grid[i][j] != 0: right[i][j] = 1 else: right[i][j] = 0 else: if grid[i][j] != 0: right[i][j] = right[i][j+1] + 1 else: right[i][j] = 0 # 填充 up 矩阵 for j in range(N): for i in range(N): if i == 0: if grid[i][j] != 0: up[i][j] = 1 else: up[i][j] = 0 else: if grid[i][j] != 0: up[i][j] = up[i-1][j] + 1 else: up[i][j] = 0 # 填充 down 矩阵 for j in range(N): for i in reversed(range(N)): if i == N-1: if grid[i][j] != 0: down[i][j] = 1 else: down[i][j] = 0 else: if grid[i][j] != 0: down[i][j] = down[i+1][j] + 1 else: down[i][j] = 0 # 计算最大k max_k = 0 for i in range(N): for j in range(N): if grid[i][j] == 1: k = min(left[i][j], right[i][j], up[i][j], down[i][j]) if k > max_k: max_k = k print(max_k)order_of_largest_plus_sign()
该方法通过预处理每个方向的最大延伸步数，确保了算法的高效性和正确性。
转载地址：http://futuz.baihongyu.com/