当前位置:   article > 正文

连连看 - 蓝桥杯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代码示例:

  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.List;
  4. import java.util.Map;
  5. import java.util.Scanner;
  6. public class ConnectPairs {
  7. public static void main(String[] args) {
  8. // 读取网格的行数和列数
  9. Scanner scanner = new Scanner(System.in);
  10. int n = scanner.nextInt(); // 行数
  11. int m = scanner.nextInt(); // 列数
  12. scanner.nextLine(); // 消耗掉输入中的换行符
  13. // 读取网格内容
  14. int[][] grid = new int[n][m];
  15. for (int i = 0; i < n; i++) {
  16. String[] row = scanner.nextLine().split("\\s+"); // 使用正则表达式分割空格
  17. for (int j = 0; j < m; j++) {
  18. grid[i][j] = Integer.parseInt(row[j]); // 将字符串转换为整数
  19. }
  20. }
  21. // 调用方法并输出结果
  22. System.out.println(countPairs(grid));
  23. scanner.close();
  24. }
  25. // 计算满足条件的格子对数量
  26. public static int countPairs(int[][] grid) {
  27. int n = grid.length; // 行数
  28. int m = grid[0].length; // 列数
  29. Map<Integer, List<int[]>> positions = new HashMap<>(); // 存储每个数字的位置
  30. // 遍历整个网格并记录每个数字的位置
  31. for (int i = 0; i < n; i++) {
  32. for (int j = 0; j < m; j++) {
  33. int num = grid[i][j]; // 获取当前位置的数字
  34. positions.putIfAbsent(num, new ArrayList<>()); // 如果该数字还未在字典中,则创建一个空列表来存储其位置
  35. positions.get(num).add(new int[]{i, j}); // 将当前位置添加到该数字的位置列表中
  36. }
  37. }
  38. int count = 0; // 计数器,用于记录符合条件的格子对数量
  39. // 遍历每个数字的位置列表
  40. for (Map.Entry<Integer, List<int[]>> entry : positions.entrySet()) {
  41. int num = entry.getKey(); // 当前数字
  42. List<int[]> positionsList = entry.getValue(); // 当前数字的所有位置
  43. // 如果该数字的位置少于2个,则跳过,因为无法形成符合条件的格子对
  44. if (positionsList.size() < 2) {
  45. continue;
  46. }
  47. // 遍历位置列表中的每对位置
  48. for (int i = 0; i < positionsList.size(); i++) {
  49. for (int j = i + 1; j < positionsList.size(); j++) {
  50. int[] a = positionsList.get(i); // 第一个位置
  51. int[] b = positionsList.get(j); // 第二个位置
  52. // 检查两个位置是否满足条件 |a[0] - b[0]| = |a[1] - b[1]| > 0
  53. if (Math.abs(a[0] - b[0]) == Math.abs(a[1] - b[1]) && Math.abs(a[0] - b[0]) > 0) {
  54. count++; // 符合条件的格子对数量加一
  55. }
  56. }
  57. }
  58. }
  59. return count; // 返回符合条件的格子对数量
  60. }
  61. }

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

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

Python代码示例:

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

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/煮酒与君饮/article/detail/907331
推荐阅读
相关标签
  

闽ICP备14008679号