华为OD机试 - 幻方修复（Java 2024 E卷 200分）

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

幻方（Magic Square）是一个由 1~N²，共 N² 个整数构成的 N*N 矩阵，满足每行、列和对角线上的数字和相等。

上回你已经帮助小明将写错一个数字的幻方进行了修复，小明在感激之余也想进一步试试你的水平，于是他准备了有两个数字发生了位置交换的幻方。

你可以把这两个交换的数字找出来并且改正吗？

二、输入描述

第一行输入一个整数 N，代表带校验幻方的阶数（3 ≤ N ≤ 50）
接下来的 N 行，每行 N 个整数，空格隔开（1 ≤ 每个整数 ≤ N²）

三、输出描述

输出两行，代表两条纠正信息，注意先输出行号小的，若行号相同则先输出列好小的

每行输出空格隔开的三个整数，分别是：出错行号、出错列号、应填入的数字（末尾无空格）

四、解题思路

输入读取：
- 使用 Scanner 从标准输入读取幻方的阶数 N。
- 读取接下来的 N 行，每行 N 个整数，构成 N*N 的幻方矩阵 square。
魔数计算：
- 魔数 M 计算公式为 M = N * (N² + 1) / 2，这是标准幻方的魔数公式。
检测错误行和列：
- 遍历每一行，计算行和是否等于魔数 M。如果不等，将该行索引记录在 wrongRows 列表中。
- 遍历每一列，计算列和是否等于魔数 M。如果不等，将该列索引记录在 wrongCols 列表中。
确定交换位置：
- 假设只有两行和两列存在错误，分别记录为 r1, r2（行索引）和 c1, c2（列索引）。
- 生成四个候选交换位置：(r1,c1) 和 (r2,c2)，以及 (r1,c2) 和 (r2,c1)。
- 尝试交换 (r1,c1) 和 (r2,c2)，并检查幻方是否恢复正确。
- 如果不正确，恢复交换，并尝试交换 (r1,c2) 和 (r2,c1)，再次检查幻方是否正确。
- 根据交换结果，输出需要修正的位置和正确的数字。
输出修正信息：
- 根据交换后的结果，输出两个需要修正的位置，格式为行号列号应填入的数字。
- 行号和列号从 1 开始计数。
辅助函数：
- swap: 用于交换幻方中两个位置的数字。
- isValidMagicSquare: 检查当前幻方是否有效（所有行、列、对角线的和等于魔数）。

五、Java算法源码

java">public class OdTest {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取幻方的阶数 Nint N = scanner.nextInt();int[][] square = new int[N][N];// 读取 N*N 的幻方数字for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {square[i][j] = scanner.nextInt();}}// 计算幻方的魔数 Mint M = N * (N * N + 1) / 2;// 记录不符合魔数的行索引List<Integer> wrongRows = new ArrayList<>();for (int i = 0; i < N; i++) {int rowSum = 0;for (int j = 0; j < N; j++) {rowSum += square[i][j];}if (rowSum != M) {wrongRows.add(i);}}// 记录不符合魔数的列索引List<Integer> wrongCols = new ArrayList<>();for (int j = 0; j < N; j++) {int colSum = 0;for (int i = 0; i < N; i++) {colSum += square[i][j];}if (colSum != M) {wrongCols.add(j);}}// 检查是否恰好有两行和两列不符合魔数if (wrongRows.size() != 2 || wrongCols.size() != 2) {// 如果不符合预期，输出错误信息并结束程序System.out.println("无法找到准确的交换位置。");scanner.close();return;}// 获取有问题的两行和两列的索引int r1 = wrongRows.get(0);int r2 = wrongRows.get(1);int c1 = wrongCols.get(0);int c2 = wrongCols.get(1);// 尝试交换 (r1, c1) 和 (r2, c2)swap(square, r1, c1, r2, c2);if (isValidMagicSquare(square, N, M)) {// 如果交换后是有效的幻方，记录需要修正的位置信息List<Correction> corrections = new ArrayList<>();corrections.add(new Correction(r1, c1, square[r1][c1]));corrections.add(new Correction(r2, c2, square[r2][c2]));// 按行号和列号排序Collections.sort(corrections);// 输出纠正信息for (Correction c : corrections) {System.out.println((c.row + 1) + " " + (c.col + 1) + " " + c.correctValue);}scanner.close();return;}// 如果不行，恢复交换swap(square, r1, c1, r2, c2);// 尝试交换 (r1, c2) 和 (r2, c1)swap(square, r1, c2, r2, c1);if (isValidMagicSquare(square, N, M)) {// 如果交换后是有效的幻方，记录需要修正的位置信息List<Correction> corrections = new ArrayList<>();corrections.add(new Correction(r1, c2, square[r1][c2]));corrections.add(new Correction(r2, c1, square[r2][c1]));// 按行号和列号排序Collections.sort(corrections);// 输出纠正信息for (Correction c : corrections) {System.out.println((c.row + 1) + " " + (c.col + 1) + " " + c.correctValue);}scanner.close();return;}// 如果以上两种交换都无法修正幻方，输出错误信息System.out.println("无法通过交换修正幻方。");scanner.close();}/*** 纠正信息类，用于存储需要修正的单元格信息*/static class Correction implements Comparable<Correction> {int row;          // 行索引int col;          // 列索引int correctValue; // 应填入的正确数字Correction(int r, int c, int v) {this.row = r;this.col = c;this.correctValue = v;}/*** 比较方法，用于按行号和列号排序*/@Overridepublic int compareTo(Correction other) {if (this.row != other.row) {return this.row - other.row;}return this.col - other.col;}}/*** 交换幻方中两个位置的数字** @param square 幻方矩阵* @param r1     第一个位置的行索引* @param c1     第一个位置的列索引* @param r2     第二个位置的行索引* @param c2     第二个位置的列索引*/private static void swap(int[][] square, int r1, int c1, int r2, int c2) {int temp = square[r1][c1];square[r1][c1] = square[r2][c2];square[r2][c2] = temp;}/*** 检查当前矩阵是否为有效的幻方** @param square 幻方矩阵* @param N      幻方的阶数* @param M      幻方的魔数* @return 如果是有效的幻方，返回 true；否则返回 false*/private static boolean isValidMagicSquare(int[][] square, int N, int M) {// 检查每一行的和是否等于魔数for (int i = 0; i < N; i++) {int rowSum = 0;for (int j = 0; j < N; j++) {rowSum += square[i][j];}if (rowSum != M) {return false;}}// 检查每一列的和是否等于魔数for (int j = 0; j < N; j++) {int colSum = 0;for (int i = 0; i < N; i++) {colSum += square[i][j];}if (colSum != M) {return false;}}// 检查主对角线的和是否等于魔数int diag1 = 0;for (int i = 0; i < N; i++) {diag1 += square[i][i];}if (diag1 != M) {return false;}// 检查副对角线的和是否等于魔数int diag2 = 0;for (int i = 0; i < N; i++) {diag2 += square[i][N - 1 - i];}if (diag2 != M) {return false;}// 如果所有行、列和对角线的和都等于魔数，则为有效幻方return true;}
}