蓝桥杯-Python组（py的哈希表）

连连看

传送门：0连连看 - 蓝桥云课

问题描述

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

输入格式

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

接下来 n 行，第 i 行包含 m 个正整数 Ai,1,Ai,2,⋯,Ai,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% 的评测用例，1≤n,m≤50；

对于所有评测用例，1≤n,m≤1000,1≤Ai,j≤1000

思路

想法很容易想，随便在纸上画画就可以知道这道题的意思是：对于（i， j）这个点去找跟他在一个对角线的元素，如果相等就可以连，就是要注意一下（1， 2）连（2， 1）之后（2， 1）也会连（1， 2）也就是最后的 ans 要乘2

在写代码前，介绍一下Python的哈希表

py的哈希表

defaultdict 和 Counter 都是 Python 中用于简化字典操作的类，可以看作是某种形式的哈希表。

• defaultdict：

  • defaultdict 是 Python 标准库 collections 模块中的一个类，它是一个字典（哈希表）的子类。与普通字典不同的是，defaultdict 会为每个不存在的键提供一个默认值，避免了访问不存在的键时引发 KeyError。
  • 在你的代码中，right = defaultdict(Counter) 意味着当你访问一个不存在的键时，它会自动创建一个 Counter 对象作为这个键的值。这非常方便，因为你可以直接使用 Counter 的方法来统计出现的次数。

• Counter：

  • Counter 也是 collections 模块中的一个类，它是一个特殊的字典，用于计数可哈希对象的数量。Counter 会将对象作为键，将其出现的次数作为值。
  • 在这段代码中，right 和 left 都是以对角线的哈希值（i + j 和 j - i）作为键，而值是 Counter，它会存储在这些对角线上的元素及其出现次数。
• defaultdict（Counter）是创建了一个二维哈希表
• 如果你不使用 Counter 而是直接使用 defaultdict，那么它将是一个一维的哈希表。在这种情况下，你可以将 defaultdict 用于存储每个键对应的值，通常是整数或其他类型的数据。

代码：

from collections import *

n, m = map(int,input().split())
g = []
for _ in range(n):
  g.append(list(map(int,input().split())))
# print(g)

l = defaultdict(Counter)
r = defaultdict(Counter)

ans = 0
for i in range(n):
  for j in range(m):
    x = g[i][j]
    ans += r[i + j][x] + l[i - j][x]
    r[i + j][x] += 1
    l[i - j][x] += 1
print(ans * 2)