算法

(对角线出发) $O(n^2)$

一开始纯暴力，存储每个数出现的坐标位置，随后在每个数的坐标位置里面不断枚举，蓝桥杯可过13个样例，Acwing 4-5个，后面根据绝对值公式推导找到了规律，枚举两个方向的对角线，注意，若某个对角线上某个数字出现了i次，它的贡献是i*(i-1)

python 代码

N = 1010
g = [[0] * N for _ in range(N)]

def dg(x, y):
    cnt = [0] * (N + 1)  # 假设元素值不大于 N
    if x == n or y == m:
        return 0  # 这个点没有正对角线
    max_n = -float('inf')
    while x <= n and y <= m:
        cnt[g[x][y]] += 1
        max_n = max(max_n, g[x][y])
        x += 1
        y += 1
    res = 0
    for i in range(1, max_n + 1):
        if cnt[i] > 1:
            res += cnt[i] * (cnt[i] - 1)
    return res

def udg(x, y):
    cnt = [0] * (N + 1)  # 假设元素值不大于 N
    if y == 1 or x == n:
        return 0
    max_n = -float('inf')
    while x <= n and y >= 1:
        cnt[g[x][y]] += 1
        max_n = max(max_n, g[x][y])
        x += 1
        y -= 1
    res = 0
    for i in range(1, max_n + 1):
        if cnt[i] > 1:
            res += cnt[i] * (cnt[i] - 1)
    return res

if __name__ == '__main__':
    n, m = map(int, input().split())
    ans = 0
    #首先处理输入
    for i in range(1, n + 1):
        tem_list = list(map(int, input().split()))
        for j in range(1, m + 1):
            g[i][j] = tem_list[j - 1]

    #接下来处理正对角线
    #首先是向下的正对角线
    for i in range(1, n + 1):
        ans += dg(i, 1)  # c表示正对角线的起始点
    #接下来是向右的正对角线
    for i in range(2, m + 1):
        ans += dg(1, i)

    #接下来处理反对角线
    #同样，首先是向右的反对角线
    for i in range(1, m + 1):
        ans += udg(1, i)
    #同样，是向下的反对角线
    for i in range(2, n + 1):
        ans += udg(i, m)

    print(ans)