题解：P11001 [蓝桥杯 2024 省 Python B] 连连看

abc1234shi · 2024-08-30 16:09:10 · 题解

题意解析

一个 n×m 的二维数组 A，问 A 中有多少对满足 A_{a,b} 与 A_{c,d} 数值相等且 a-c 的绝对值等于 b-d 的绝对值，以及 a-c 的绝对值与 b-d 的绝对值都大于 0，其实就是 |a - c| = |b - d| 并且 a≠c 以及 b≠d，也可以理解成求每一条对角线上相同的数字总共有多少对（读起来有些拗口，建议多理解几遍）。求绝对值可以使用 abs 函数。

前话

数据范围很大，目标时间复杂度 O(n^2)。

思路：对于每个元素，判断对 X 型方向上有无相同元素。因为矩阵斜行的下标满足 (i+j)%2000 和 (i-j)%2000 是相等的，可以参考八皇后问题。

那么我们要用什么实现呢？哈希是一个很好的选择，因为它允许我们根据数字快速查找其位置列表。

前置知识

• 哈希是一种将任意长度输入转化为固定长度输出的算法，具有唯一性、固定性、不可逆性和确定性。常见用途包括数据完整性验证、密码存储、数字签名和哈希表。可以把哈希表理解为一种高级的数组，这种数组的下标可以是很大的整数，浮点数，字符串甚至结构体。手写哈希代码如下：

int hash(string& key) {
unsigned int hash1 = 0;
for (char ch : key) {
    hash1 = (hash1 << 5) + ch; //将每个字符的ASCII码值左移5位，然后相加 
}
return hash1;
}

这个哈希函数使用了简单的乘法和位移操作来计算字符串的哈希值。

• abs 函数用于计算整数或浮点数的绝对值（非负值）。abs 函数用法如下（假设我们要求绝对值的数为 x）：

abs(x);

其中 x 为要计算绝对值的整数或浮点数。返回结果与 x 类型相同，负数取绝对值，零返回 0，正数返回自身（说白了就是输出去掉符号的 x）。

思路解析：

建立一个变量 ans 表示答案，也就是有多少对这样的格子满足条件。

首先，需要读取网格的行数和列数，以确定网格的大小。

然后，逐行读取网格中的数字，并将它们存储在二维数组 hashmap（或列表的列表）中。

遍历网格，对于每个数字，检查它是否已经在哈希中。如果不在，则在中为它创建一个新的位置列表。如果在，则将其当前位置（行和列）添加到该数字的位置列表中。

遍历 hashmap 中的每个数字及其位置列表。 对于每个数字，如果其位置列表中的位置数量少于 2 个，则跳过，因为无法形成符合条件的格子对。

否则，遍历该数字的位置列表中的每对位置（使用两个嵌套的循环）。

对于每对位置，检查它们是否满足条件：行差的绝对值等于列差的绝对值，并且这个差值大于 0（即它们不在同一行或同一列上）。 如果满足条件，则 ans+1。

最后输出 ans 即可。

关键点

• 双重循环：在检查位置对时，我们使用了两个嵌套的循环来遍历位置列表中的每对位置。
• 条件判断：确保我们检查的位置对满足条件，即它们不在同一行或同一列上，并且它们的行差和列差的绝对值相等。

后话

我们的代码通过遍历网格并记录每个数字的位置，然后比较这些位置是否满足条件 |a - c| = |b - d| > 0 来计算符合条件的格子对数量。

在比较时，我们还确保了对角线距离大于 0，以避免计算到相同位置的格子对。