华为OD机试 – 学生方阵 – 矩阵（Java 2023 B卷 200分）

目录

• • 专栏导读
  • 一、题目描述
  • 二、输入描述
  • 三、输出描述
  • • 1、输入
    • 2、输出
  • 四、解题思路
  • • 1、题目解析
    • 2、解体思路
  • 五、Java算法源码
  • • 再重新读一遍题目，看看能否优化一下~
  • 六、效果展示
  • • 1、输入
    • 2、输出
    • 3、说明

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

专栏导读

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

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

学校组织活动，将学生排成一个矩形方阵。请在矩形方阵中找到最大的位置相连的男生数量。

这个相连位置在一个直线上，方向可以是水平的，垂直的，成对角线的或者呈反对角线的.注:学生个数不会超过10000。

二、输入描述

输入的第一行为矩阵的行数和列数，接下来的n行为矩阵元素，元素间用”,”分隔。

三、输出描述

输出一个整数，表示矩阵中最长的位置相连的男生个数。

1、输入

3,4
F,M,M,F
F,M,M,F
F,F,F,M

2、输出

3

四、解题思路

1、题目解析

本题的解题思路其实不难，遍历查找矩阵中每一个 M 点，然后求该 M 点的水平、垂直、正对角线、反对角线四个方向的 M 点个数，然后保留最大的个数

2、解体思路

1. 定义矩阵matrix，并初始化；
2. 定义矩阵中最长的位置相连的男生个数max；
3. 遍历矩阵，并跳过女生M；
4. 计算每行相连的男生个数；
5. 计算每列相连的男生个数；
6. 计算斜线相连的男生个数；
7. 计算反斜线相连的男生个数；
8. 相连最大值。

五、Java算法源码

public class OdTest03 {
    static int m, n = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(",");
        // m行
        m = Integer.valueOf(input[0]);
        // n列
        n = Integer.valueOf(input[1]);
        // 矩阵
        String[][] matrix = new String[m][n];
        for (int i = 0; i < m; i++) {
            String[] line = sc.nextLine().split(",");
            for (int j = 0; j < n; j++) {
                matrix[i][j] = line[j];
            }
        }

        // 矩阵中最长的位置相连的男生个数
        int max = 0;
        // 遍历矩阵
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                String compare = matrix[i][j];
                // 跳过女生M
                if (compare.equals("F")) {
                    continue;
                }

                // 计算每行相连的男生个数
                int rowSame = getSameRowMax(matrix, compare, i, j);
                // 计算每列相连的男生个数
                int columnSame = getSameColumnMax(matrix, compare, i, j);
                // 计算斜线相连的男生个数
                int obliqueSame = getSameObliqueMax(matrix, compare, i, j);
                // 计算反斜线相连的男生个数
                int reverseObliqueSame = getSameReverseObliqueMax(matrix, compare, i, j);
                int maxSame = Integer.max(Integer.max(columnSame, rowSame), Integer.max(obliqueSame, reverseObliqueSame));
                if (maxSame >= max) {
                    max = maxSame;
                }
            }
        }
        System.out.println(max);
    }

    /**
     * 计算每行相连的男生个数
     *
     * @param matrix  矩阵
     * @param compare 待比较字符
     * @param i       行
     * @param j       列
     * @return 相连的男生个数
     */
    private static int getSameRowMax(String[][] matrix, String compare, int i, int j) {
        int same = 1;
        for (int k = j + 1; k < n; k++) {
            // 比较同一行中下一列字符
            if (compare.equals(matrix[i][k])) {
                same++;
            } else {
                // 如果不同，终止遍历，返回当前行相连的男生个数
                break;
            }
        }
        return same;
    }

    // 计算每列相连的男生个数
    private static int getSameColumnMax(String[][] matrix, String compare, int i, int j) {
        int same = 1;
        for (int k = i + 1; k < m; k++) {
            // 比较同一列中的下一行字符
            if (compare.equals(matrix[k][j])) {
                same++;
            } else {
                // 如果不同，终止遍历，返回当前列相连的男生个数
                break;
            }
        }
        return same;
    }

    // 计算斜线相连的男生个数
    private static int getSameObliqueMax(String[][] matrix, String compare, int i, int j) {
        int same = 1;
        for (int k = i + 1; k < m; k++) {
            for (int l = j + 1; l < n; l++) {
                // 比较下一行下一列处于斜线上的下一个字符
                if (compare.equals(matrix[k][l])) {
                    same++;
                } else {
                    // 如果不同，终止遍历，返回当前斜线相连的男生个数
                    return same;
                }
                break;
            }
        }
        return same;
    }

    // 计算反斜线相连的男生个数
    private static int getSameReverseObliqueMax(String[][] matrix, String compare, int i, int j) {
        if (i == 0) {
            return 1;
        }

        int same = 1;
        for (int k = i + 1; k < m; k++) {
            for (int l = j - 1; l >= 0; l--) {
                // 比较下一行下一列处于斜线上的下一个字符
                if (compare.equals(matrix[k][l])) {
                    same++;
                } else {
                    // 如果不同，终止遍历，返回当前斜线相连的男生个数
                    return same;
                }
                break;
            }
        }
        return same;
    }
}

感觉这道题，不至于这么复杂吧。

再重新读一遍题目，看看能否优化一下~

优化关键点：

1. 定义方向二位数组direction；
2. 遍历矩阵，如果前一个是M，表示此M已经计算过了，直接跳过；
3. 简化上面的4种遍历方法，通过累加direction中的横纵坐标，计算每行、每列、斜线、反斜线相连的男生个数，并取相连最大值。

public class OdTest {
    static int m, n = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(",");
        // m行
        m = Integer.valueOf(input[0]);
        // n列
        n = Integer.valueOf(input[1]);
        // 矩阵
        String[][] matrix = new String[m][n];
        for (int i = 0; i < m; i++) {
            String[] line = sc.nextLine().split(",");
            for (int j = 0; j < n; j++) {
                matrix[i][j] = line[j];
            }
        }

        /**
         * 数组的第0位-行、数组的第1位-列
         * {0,1}寻找一行内连续的M
         * {1,0}寻找一列中连续的M
         * {1,1}寻找斜下中连续的M
         * {1,-1}寻找反斜下连续的M
         */
        int[][] direction = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};

        // 矩阵中最长的位置相连的男生个数
        int max = 0;
        // 遍历矩阵
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j].equals("M")) {
                    for (int[] arr : direction) {
                        int reverseI = i - arr[0];
                        int reverseJ = j - arr[1];

                        // 如果前一个是M，表示此M已经计算过了，直接跳过
                        if (reverseI >= 0 && reverseI < m && reverseJ >= 0 && reverseJ < n && matrix[reverseI][reverseJ].equals("M")) {
                            continue;
                        }

                        int nextI = i + arr[0];
                        int nextJ = j + arr[1];
                        int same = 1;

                        // 计算每行、每列、斜线、反斜线相连的男生个数，并取相连最大值
                        while (nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n && matrix[nextI][nextJ].equals("M")) {
                            same++;
                            nextI += arr[0];
                            nextJ += arr[1];
                        }

                        max = Integer.max(max, same);
                    }
                }
            }
        }
        System.out.println(max);
    }
}

六、效果展示

1、输入

7,8
F,M,M,F,M,M,M,M
F,M,M,M,F,F,F,F
F,F,F,M,M,F,F,F
F,F,F,M,M,M,F,F
F,F,F,F,F,M,F,F
F,F,F,M,F,M,F,F
F,F,F,M,F,M,F,M

2、输出

5

3、说明

🏆下一篇：华为OD机试 – 最长的顺子 – 感谢@禁止你发言提供的更简便算法（Java 2023 B卷 200分）

🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。