连连看 - 蓝桥杯2024年第十五届省赛真题

基础知识要求：

Java：Scanner类、方法、for循环、集合、数组、Math类

Python： 方法、for循环、字典、if判断、列表、map()、abs()、input()

题目： 

小蓝正在和朋友们玩一种新的连连看游戏。在一个 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 。

思路解析：

1. 读取输入：
   • 首先，我们需要读取网格的行数和列数，以确定网格的大小。
   • 然后，我们逐行读取网格中的数字，并将它们存储在二维数组（或列表的列表）中。
2. 存储位置信息：
   • 创建一个数据结构（如HashMap）来存储每个数字在网格中的位置。
   • 遍历网格，对于每个数字，检查它是否已经在HashMap中。如果不在，则在HashMap中为它创建一个新的位置列表；如果在，则将其当前位置（行和列）添加到该数字的位置列表中。
3. 检查位置对：
   • 遍历HashMap中的每个数字及其位置列表。
   • 对于每个数字，如果其位置列表中的位置数量少于2个，则跳过，因为无法形成符合条件的格子对。
   • 否则，遍历该数字的位置列表中的每对位置（使用两个嵌套的循环）。
   • 对于每对位置，检查它们是否满足条件：行差的绝对值等于列差的绝对值，并且这个差值大于0（即它们不在同一行或同一列上）。
   • 如果满足条件，则增加计数器。
4. 输出结果：
   • 返回计数器的值，即满足条件的格子对数量。

关键点

• 数据结构的选择：HashMap是一个很好的选择，因为它允许我们根据数字快速查找其位置列表。
• 双重循环：在检查位置对时，我们使用了两个嵌套的循环来遍历位置列表中的每对位置。
• 条件判断：确保我们检查的位置对满足条件，即它们不在同一行或同一列上，并且它们的行差和列差的绝对值相等。

Java代码示例：

import java.util.ArrayList;  
import java.util.HashMap;  
import java.util.List;  
import java.util.Map;  
import java.util.Scanner;  public class ConnectPairs {  public static void main(String[] args) {  // 读取网格的行数和列数  Scanner scanner = new Scanner(System.in);  int n = scanner.nextInt(); // 行数  int m = scanner.nextInt(); // 列数  scanner.nextLine(); // 消耗掉输入中的换行符  // 读取网格内容  int[][] grid = new int[n][m];  for (int i = 0; i < n; i++) {  String[] row = scanner.nextLine().split("\\s+"); // 使用正则表达式分割空格  for (int j = 0; j < m; j++) {  grid[i][j] = Integer.parseInt(row[j]); // 将字符串转换为整数  }  }  // 调用方法并输出结果  System.out.println(countPairs(grid));  scanner.close();  }  // 计算满足条件的格子对数量  public static int countPairs(int[][] grid) {  int n = grid.length; // 行数  int m = grid[0].length; // 列数  Map<Integer, List<int[]>> positions = new HashMap<>(); // 存储每个数字的位置  // 遍历整个网格并记录每个数字的位置  for (int i = 0; i < n; i++) {  for (int j = 0; j < m; j++) {  int num = grid[i][j]; // 获取当前位置的数字  positions.putIfAbsent(num, new ArrayList<>()); // 如果该数字还未在字典中，则创建一个空列表来存储其位置  positions.get(num).add(new int[]{i, j}); // 将当前位置添加到该数字的位置列表中  }  }  int count = 0; // 计数器，用于记录符合条件的格子对数量  // 遍历每个数字的位置列表  for (Map.Entry<Integer, List<int[]>> entry : positions.entrySet()) {  int num = entry.getKey(); // 当前数字  List<int[]> positionsList = entry.getValue(); // 当前数字的所有位置  // 如果该数字的位置少于2个，则跳过，因为无法形成符合条件的格子对  if (positionsList.size() < 2) {  continue;  }  // 遍历位置列表中的每对位置  for (int i = 0; i < positionsList.size(); i++) {  for (int j = i + 1; j < positionsList.size(); j++) {  int[] a = positionsList.get(i); // 第一个位置  int[] b = positionsList.get(j); // 第二个位置  // 检查两个位置是否满足条件 |a[0] - b[0]| = |a[1] - b[1]| > 0  if (Math.abs(a[0] - b[0]) == Math.abs(a[1] - b[1]) && Math.abs(a[0] - b[0]) > 0) {  count++; // 符合条件的格子对数量加一  }  }  }  }  return count; // 返回符合条件的格子对数量  }  
}

在这个 Java 程序中，我们首先使用 Scanner 类从标准输入读取网格的行数、列数和内容。然后，我们使用一个 HashMap 来存储每个数字在网格中的所有位置。我们使用一个 int[] 数组来表示每个位置（行和列）。

在 countPairs 方法中，我们遍历了每个数字的位置列表，并检查每对位置是否满足条件 |a[0] - b[0]| = |a[1] - b[1]| > 0。如果满足条件，则计数器 count 增加。最后，我们返回计数器的值作为结果。

Python代码示例：

def count_pairs(grid):  # 初始化变量  n, m = len(grid), len(grid[0])  # 获取网格的行数和列数  positions = {}  # 创建一个字典，用于存储每个数字的所有位置  count = 0  # 初始化计数器，用于记录符合条件的格子对数量  # 遍历整个网格并记录每个数字的位置  for i in range(n):  for j in range(m):  num = grid[i][j]  # 获取当前位置的数字  if num not in positions:  # 如果该数字还未在字典中，则创建一个空列表来存储其位置  positions[num] = []  positions[num].append((i, j))  # 将当前位置添加到该数字的位置列表中  # 遍历每个数字的位置列表  for num, positions_list in positions.items():  # 如果该数字的位置少于2个，则跳过，因为无法形成符合条件的格子对  if len(positions_list) < 2:  continue  # 对位置列表中的每对位置进行遍历  for i in range(len(positions_list)):  for j in range(i+1, len(positions_list)):  # 获取两个位置的坐标  a, b = positions_list[i]  c, d = positions_list[j]  # 检查两个位置是否满足条件 |a - c| = |b - d| > 0  if abs(a - c) == abs(b - d) and abs(a - c) > 0:  # 确保对角线距离大于0  count += 1  # 符合条件的格子对数量加一  return count  # 返回符合条件的格子对数量  # 读取输入  
n, m = map(int, input().split())  # 读取网格的行数和列数  
grid = []  
for _ in range(n):  grid.append(list(map(int, input().split())))  # 读取每一行的数字，并转换为整数列表  # 调用函数并输出结果  
print(count_pairs(grid))  # 调用 count_pairs 函数并打印结果

这段代码通过遍历网格并记录每个数字的位置，然后比较这些位置是否满足条件 |a - c| = |b - d| > 0 来计算符合条件的格子对数量。在比较时，我们还确保了对角线距离大于0，以避免计算到相同位置的格子对