M25570: 洋葱

matrices, http://cs101.openjudge.cn/practice/25570/

“如果你愿意一层一层一层地剥开我的心，你会发现，你会讶异，你是我最压抑最深处的秘密”

我们将洋葱抽象为一个n*n的矩阵，绕着矩阵最外侧环绕一圈，即得到一个“层”，然后将这个“层”中所有元素去掉，得到一个子矩阵，重复上述操作，即可得到若干个“层”。显然，若n为奇数，则位于其中心的那一个元素也构成一个“层”。

现在给小明一个n*n的矩阵，小明想找到这个矩阵的“最大层”。“最大层”即为该矩阵每个“层”中数字之和最大的那个。

输入

第一行一个正整数n (n <= 100) 接下来n行，每行n个整数，代表矩阵中各个位置的数，均为不大于10000的非负整数

输出

一个整数，代表矩阵的“最大层”中的各数之和

样例输入

5
1 0 1 0 1
0 1 1 1 0
0 1 7 1 0
0 1 1 1 0
1 0 1 0 1

样例输出

8

解释：
在样例中，该矩阵共有三个“层”
1+0+1+0+1+0+0+0+1+0+1+0+1+0+0+0=6
1+1+1+1+1+1+1+1=8
7

所以“最大层”中的各数之和是8

提示

tags: matrices

来源：2022fall-cs101, gdr

思路：

• 旋转矩阵的另一个版本罢了
• 通过N // 4紧凑地表示出所处层数

# 颜鼎堃 24工学院
DIRECTIONS = ((0, 1), (1, 0), (0, -1), (-1, 0))
n = int(input())
N = 0
onion = [[-1e9 for i in range(n + 2)]] + [[-1e9] + list(map(int, input().split())) + [-1e9] for i in range(n)] + [[-1e9 for i in range(n + 2)]]
dx, dy = DIRECTIONS[0]
x, y = 1, 0
layer = [0 for i in range(n // 2 + 1)]
for i in range(1, 1 + n * n):
    if onion[x + dx][y + dy] == -1e9:
        N += 1
        dx, dy = DIRECTIONS[N % 4]
    x, y = x + dx, y + dy
    layer[N // 4] += onion[x][y]
    onion[x][y] = -1e9
print(max(layer))

【靳熙恒 25物理学院】思路：按照题面实现即可。需要注意的一个小细节是，如果是奇数阶矩阵，到最后一层就只剩一个元素，这种情况需要特殊处理一下。

from collections import deque

def lv_sum(matrix_deque):
    if len(matrix_deque) == 1:
        row = matrix_deque[0]
        if len(row) == 1:
            return row[0]
        else:
            # 弹出首尾（如果还有多个元素）
            return row.popleft() + row.pop()
    
    top = matrix_deque.popleft()
    bottom = matrix_deque.pop()
    ans = sum(top) + sum(bottom)
    
    for row in matrix_deque:
        if len(row) > 1:
            ans += row.popleft() + row.pop()
        elif len(row) == 1:
            ans += row.pop()  # 或 popleft()，效果一样
    
    return ans

n = int(input())
data = []
for _ in range(n):
    data.append(deque(map(int, input().split())))

# 将整个 matrix 转为 deque of deques
matrix_deque = deque(data)

max_sum = 0
for _ in range((n + 1) // 2):
    current_sum = lv_sum(matrix_deque)
    max_sum = max(max_sum, current_sum)

print(max_sum)

# 汤伟杰，24信息管理系
def dfs(n, s, x, y):
    # 递归的终止条件
    if n == 1:
        return s[x][y]  # 如果只剩一个元素，直接返回该元素值
    if n == 0:
        return 0  # 空矩阵返回0

    # 记录当前边缘的累加和
    curr = 0
    # 定义方向向量：右、下、左、上
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    # 遍历边缘的元素，总共需要遍历 4 * (n - 1) 个元素
    for i in range(4 * (n - 1)):
        dx, dy = directions[(i // (n - 1)) % 4]  # 根据当前索引计算方向
        x += dx
        y += dy
        curr += s[x][y]

    # 递归到下一层，矩阵缩小一圈，起始坐标向内移动一格
    return max(curr, dfs(n - 2, s, x + 1, y + 1))


# 输入部分
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]

# 初始调用 dfs
result = dfs(n, s, 0, 0)
print(result)

思路：和螺旋矩阵类似，只要见过一次就不新鲜了

# 刘家亦、物院
import math
n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
sums = [0] * math.ceil(n / 2)
if n % 2 == 1:
    sums[-1] = matrix[math.ceil(n / 2) - 1][math.ceil(n / 2) - 1]
for layer in range(math.ceil(n / 2)):
    i, j = layer, layer
    for di, dj in directions:
        for _ in range(n - layer * 2 - 1):
            sums[layer] += matrix[i][j]
            i += di
            j += dj
print(max(sums))

逐层检索找到最大即可

# 李天笑、24物理学院
n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]
ans = float('-inf')
for i in range((n + 1) // 2):
    cur_ans = 0
    if i != n - 1 - i:
        cur_ans += sum(matrix[i][i: n - i])
        cur_ans += sum(matrix[n - 1 - i][i: n - i])
        for j in range(i + 1, n - i - 1):
            cur_ans += matrix[j][n - i - 1]
            cur_ans += matrix[j][i]
    if i == n - 1 - i:
        cur_ans += sum(matrix[i][i: n - i])
        
        
    ans = max(cur_ans, ans)
print(ans)

思路：不需要存把"洋葱"存下来,读一行比一行

#杨馨尧, 24物理学院
n = int(input())
buffer = [0] * ((n+1)//2+1)
for i in range(1, n+1):
    line = [0]+list(map(int, input().split()))
    for j in range(1, n+1):
        k = min(i, j, (n+1)-i, (n+1)-j)
        buffer[k] += line[j]
print(max(buffer))

曼哈顿距离，也被称为城市街区距离（City block distance）、L1距离或出租车几何，是衡量在标准坐标系上两点之间的距离的一种方法。它定义为两个点在各个维度上的绝对差值之和。

对于二维平面上的两个点 (A(x_1, y_1)) 和 (B(x_2, y_2))，它们之间的曼哈顿距离可以通过下面的公式计算：

[d(A, B) = |x_1 - x_2| + |y_1 - y_2|]

这个概念可以推广到更高维度的空间。例如，在n维空间中，对于两个点 (A(x_1, x_2, ..., x_n)) 和 (B(y_1, y_2, ..., y_n))，它们之间的曼哈顿距离为：

[d(A, B) = |x_1 - y_1| + |x_2 - y_2| + ... + |x_n - y_n|]

曼哈顿距离的名字来源于美国纽约市曼哈顿区的街道布局，那里大多数道路要么是东西走向，要么是南北走向，形成网格状。因此，如果要从一个地方到达另一个地方，你不能直接走斜线（就像欧几里得距离那样），而是必须沿着这些垂直或水平的道路移动，这正是曼哈顿距离所模拟的情况。

曼哈顿距离的应用非常广泛，包括但不限于计算机视觉、聚类分析、路径规划等领域。例如，在图像处理中，它可以用来度量两个像素点的颜色差异；在机器学习中，它可以作为不同类型的聚类算法的距离度量标准；在机器人技术中，它可以用作导航算法中的代价函数等。

2022fall-cs101，张宇辰，元培学院。看了一下OJ里大家的代码长度，我这个解法应该差不多是最简洁也是最干净的，老师如果觉得还行可以考虑收入题解。

将Matrix中的每个数归到第某圈洋葱的和即可。

from math import ceil
n = int(input()) 
matrix = [0 for _ in range(n)] 
for i in range(n): 
    matrix[i] = [int(_) for _ in input().split()] 
ans = [0] * ceil(n/2) 
for i in range(n): 
    for j in range(n): 
        ans[min(i, j, n-1-i, n-1-j)] += matrix[i][j] 
print(max(ans))

ans = [0] * ceil(n/2)：创建一个长度为ceil(n/2)的列表，所有元素初始值都为0。这个列表用于存储特定模式下元素之和的结果。之所以使用ceil(n/2)是因为对于任意一对对称位置(i, j)和(n-1-i, n-1-j)，它们会映射到同一个索引上；对于奇数大小的矩阵，中心元素也会单独映射到一个索引。

在这道题中，min(i, j, n-1-i, n-1-j) 的使用是为了确定当前元素属于哪一个“层”。这里的“层”指的是从外到内围绕着矩阵中心的环形区域。每一层都包括了距离矩阵边缘相同距离的所有元素。

让我们来具体分析一下 min(i, j, n-1-i, n-1-j)：

• i 是当前行索引。
• j 是当前列索引。
• n-1-i 是从矩阵底边到当前元素的距离。
• n-1-j 是从矩阵右边到当前元素的距离。

通过取这四个值中的最小值，我们可以得到当前元素离最近的边界有多远，这个距离实际上就对应了它所在的“层”的编号（假设最外层为第0层）。例如，在一个5x5的矩阵中：

• 如果元素位于角落（比如 (0,0)），那么 min(0, 0, 4, 4) 将给出 0，表示这是最外层。
• 对于靠近中心但不在最中心的元素（比如 (1,2)），min(1, 2, 3, 2) 将给出 1，意味着这是第二层。
• 中心元素 (对于奇数大小的矩阵)，如 (2,2)，将给出 min(2, 2, 2, 2)，即也是 2，这将是最后一层（如果 n = 5）。

因此，当你遍历整个矩阵时，min(i, j, n-1-i, n-1-j) 可以帮助你识别出每个元素所属的层，并正确地将它们累加到对应的层总和中。在代码中，ans[min(i, j, n-1-i, n-1-j)] += matrix[i][j] 这一行就是基于上述逻辑工作的，确保每个元素都被加到了正确的层中，最终可以找到“最大层”的和。

在提供的例子中，矩阵有三个不同的“层”，分别是：

• 最外层：由所有边界上的元素组成，其元素之和为6。
• 第二层：由内部一层的元素组成，其元素之和为8。
• 中心层：仅包含中心元素7。

所以，“最大层”的元素之和是8。

思路：懒得费尽心思想什么很多东西了

# 李欣妤、24地空学院
import math
n = int(input())
onion = []
for i in range(n):
    onion.append(list(map(int, input().split())))
layers = math.ceil(n/2)
sums = []
def sum_layer(onion, l_u, r_d):
    sum = 0
    for i in range(l_u, r_d + 1):
        sum += onion[l_u][i]  # 上
        sum += onion[r_d][i]  # 下
        sum += onion[i][l_u]  # 左
        sum += onion[i][r_d]  # 右
    # 减去四个角，因为它们被加了两次
    sum -= onion[l_u][l_u]
    sum -= onion[r_d][r_d]
    sum -= onion[r_d][l_u]
    sum -= onion[l_u][r_d]
    if l_u == r_d:
        sum += onion[l_u][r_d]
    return sum

for i in range(layers):
    sums.append(sum_layer(onion, i, n - 1 - i))
print(max(sums))

def max_layer_sum(n, matrix):
    # 初始化结果数组，长度为半径+1，因为索引是从0开始的
    layer_sums = [0] * ((n + 1) // 2)
    
    # 遍历矩阵中的每个元素
    for i in range(n):
        for j in range(n):
            # 对于奇数尺寸矩阵，最后一层可能只有一个中心元素
            layer_index = min(i, j, n - 1 - i, n - 1 - j)
            layer_sums[layer_index] += matrix[i][j]
    
    # 返回所有层中元素和的最大值
    return max(layer_sums)

# 获取输入
n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]

# 调用函数并打印结果
print(max_layer_sum(n, matrix))

def max_layer_sum(n, matrix):
    # 初始化结果列表，用于存储每一层的和
    layer_sums = []

    # 计算每一层的和
    for layer in range((n + 1) // 2):
        layer_sum = 0
        # 上边缘
        for i in range(layer, n - layer):
            layer_sum += matrix[layer][i]
        # 右边缘
        for i in range(layer + 1, n - layer):
            layer_sum += matrix[i][n - layer - 1]
        # 下边缘
        for i in range(layer + 1, n - layer):
            layer_sum += matrix[n - layer - 1][n - i - 1]
        # 左边缘
        for i in range(layer + 1, n - layer - 1):
            layer_sum += matrix[n - i - 1][layer]

        # 添加当前层的和到结果列表
        layer_sums.append(layer_sum)

    # 返回最大层的和
    return max(layer_sums)

# 输入处理
n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]

# 输出最大层的和
print(max_layer_sum(n, matrix))

根据给定的层号 layer\text{layer}，我们可以确定当前层的边界：

• 每一层由矩阵的 上边缘、右边缘、下边缘、左边缘 组成。

• 对于层号

  layer\text

  ，它的边界定义如下：

  • 上边缘: 行号为 layer\text{layer}，列号从 layer\text{layer} 到 n−layer−1n - \text{layer} - 1。
  • 右边缘: 列号为 n−layer−1n - \text{layer} - 1，行号从 layer+1\text{layer} + 1 到 n−layer−1n - \text{layer} - 1。
  • 下边缘: 行号为 n−layer−1n - \text{layer} - 1，列号从 n−layer−2n - \text{layer} - 2 到 layer\text{layer}（从右往左）。
  • 左边缘: 列号为 layer\text{layer}，行号从 n−layer−2n - \text{layer} - 2 到 layer+1\text{layer} + 1（从下往上）。

通过这些边界，可以完整地遍历某一层的所有元素。

---

举例说明

假设 n=5n = 5，矩阵如下：

1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

Layer = 0

• 上边缘：1 2 3 4 5
• 右边缘：10 15 20 25
• 下边缘：24 23 22 21
• 左边缘：16 11 6

Layer = 1

• 上边缘：7 8 9
• 右边缘：14 19
• 下边缘：18 17 16
• 左边缘：12

Layer = 2 (中心)

• 上边缘：13

思路：额，感觉正常遍历即可。（10分钟）

# 王沛然，24物理学院
n=int(input())
sl=[]
for _ in range(n):
    sl.append(list(map(int,input().split())))
nl=[]
while True:
    if n==0:
        break
    elif n==1:
        nl.append(sl[0][0])
        break
    z=0
    z+=sum(sl[0])+sum(sl[n-1])
    for i in range(1,n-1):
        z+=sl[i][0]+sl[i][n-1]
        del sl[i][0]
        del sl[i][n-2]
    del sl[0]
    del sl[n-2]
    nl.append(z)
    n-=2
    continue
print(max(nl))

删除每行的头部和尾部元素，复杂度是O(n)。所以换用deque，deque套deque，构造matrix，还挺方便。

from collections import deque

n = int(input())
sl = deque()
for _ in range(n):
    sl.append(deque(map(int, input().split())))

nl = []

while True:
    if n == 0:
        break
    elif n == 1:
        nl.append(sl[0][0])  # 只剩一个元素时，直接添加并结束
        break

    # 计算当前矩阵外圈的元素和
    z = sum(sl[0]) + sum(sl[-1])  # 顶部和底部行
    for i in range(1, n - 1):
        z += sl[i][0] + sl[i][-1]  # 左右两列

    # 添加当前外圈的总和
    nl.append(z)

    # 去除当前外圈
    sl.popleft()  # 删除顶部行
    sl.pop()      # 删除底部行
    for i in range(len(sl)):
        sl[i].popleft()  # 删除每行的左侧元素
        sl[i].pop()      # 删除每行的右侧元素

    # 矩阵维度减小
    n -= 2

# 输出结果
print(max(nl))