hash

例题

连连看

问题描述

小蓝正在和朋友们玩一种新的连连看游戏。在一个 n×m 的矩形网格中，每个格子中都有一个整数，第 i 行第 j 列上的整数为 ​ 。玩家需要在这个网格中寻找一对格子 (a,b)−(c,d) 使得这两个格子中的整数 ​ 和 ​ 相等，且它们的位置满足 ∣a−c∣=∣b−d∣>0 。请问在这个 n×m 的矩形网格中有多少对这样的格子满足条件。

输入格式:

输入的第一行包含两个正整数 n,m，用一个空格分隔。

接下来 n 行，第 i 行包含 m 个正整数 ​，相邻整数之间使用一个空格分隔。

输出格式:

输出一行包含一个整数表示答案。

样例输入

3 2
1 2
2 3
3 2

样例输出

6

样例说明

一共有以下 6 对格子：(1,2)−(2,1)，(2,2)−(3,1)，(2,1)−(3,2)，(2,1)−(1,2)，(3,1)−(2,2)，(3,2)−(2,1)。

评测用例规模与约定

对于 20%的评测用例，

对于所有评测用例，

from collections import defaultdict

def count_pairs(n, m, grid):
    # 按值分组 (hash_map)
    value_positions = defaultdict(list) # {值: [(行, 列), ...]}
    for i in range(n):
        for j in range(m):
            value_positions[grid[i][j]].append((i, j))
    # {
    #    1: [(1, 1), (3, 3)],
    #    2: [(1, 2), (1, 3), (2, 1), (3, 2)],
    #    3: [(2, 2), (2, 3), (3, 1)],
    # }
    total_pairs = 0

    # 遍历每个值的分组
    for value, positions in value_positions.items(): # [(k,v), ...]
        # 统计主对角线 (a - b) 和副对角线 (a + b)
        main_diag = defaultdict(int)
        anti_diag = defaultdict(int)
        # 如果  |a - c| = |b - d| ，则它们的对角线差值  a - b  或对角线和  a + b  是相同的
        for x, y in positions: # [(x1, y1), (x2, y2), ...]
            main_diag[x - y] += 1 # 主对角线上的点满足 x - y = k
            anti_diag[x + y] += 1 # 副对角线上的点满足 x + y = k

        # 计算主对角线上的对数
        for count in main_diag.values(): # [v, ...]
            if count > 1:
                total_pairs += count * (count - 1) // 2

        # 计算副对角线上的对数
        for count in anti_diag.values():
            if count > 1:
                total_pairs += count * (count - 1) // 2

    return total_pairs * 2  # 该题目要求每对 (i, j) 和 (j, i) 都算一次，所以乘以 2

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

# 输出结果
print(count_pairs(n, m, grid))