dp

不出意料的tle了

n,m=map(int,input().split())
dx=[-1,-1,1,1]
dy=[-1,1,1,-1]
ans=0

mp=[]
for i in range(n):
    line=list(map(int,input().split()))
    mp.append(line)

for i in range(n):
    for j in range(m):
        x=i
        y=j
        for k in range(4):
            tx=x+dx[k]
            ty=y+dy[k]
            while 0<=tx<n and 0<=ty<m:
                if mp[tx][ty]==mp[x][y]:
                    ans+=1
                tx+=dx[k]
                ty+=dy[k]
print(ans)

哈希

计算出所有正对角线和负对角线
用哈希表统计每条线上数字出现的次数

对角线

若要枚举一个 n * m 方格的所有斜对角线，可按以下步骤操作：

• 正斜对角线：
  从方格的左上角到右下角方向。
  每条正斜对角线的元素坐标 (i, j) 满足 i + j 为固定值，其范围是从 0 到 n + m - 2。

• 反斜对角线：
  从方格的右上角到左下角方向。
  每条反斜对角线的元素坐标 (i, j) 满足 i - j 为固定值，其范围是从 -(m - 1) 到 n - 1。

个人觉得比较难的点

• 在枚举的时候，neg[i-j+m-1].append(mp[i][j])
  因为反斜对角线取值范围为 -(m - 1) 到 n - 1，使其+(m-1)，调整后的索引范围是 0 到 n + m - 2，正好对应列表的长度 n + m - 1。

• 最后计算答案ans+=(x-1)x
  因为若一条线上同为2的方格有x个，那么也就是在x个数中选出2个数的组合数，C(x,2)，且这个组合数需要2，对于题目来说(a,b)，(b,a)是两个组合。

C(x,2)=(x-1)*x//2
ans+=C(x,2)*2

from collections import Counter

n, m = map(int, input().split())
mp = [list(map(int, input().split())) for _ in range(n)]
ans = 0
pos=[[] for _ in range(n + m - 1)]
neg=[[] for _ in range(n + m - 1)]

for i in range(n):
    for j in range(m):
        pos[i+j].append(mp[i][j])
        neg[i-j+m-1].append(mp[i][j])

for i in range(n+m-1):
    c=Counter(pos[i])
    for j in c:
        x=c[j]
        ans+=(x-1)*x

    c=Counter(neg[i])
    for j in c:
        x=c[j]
        ans+=(x-1)*x

print(ans)