美团2024届秋招笔试第一场编程真题——小美的好矩阵

现在给定一个n∗m的矩阵，小美想知道有多少个3*3的子矩阵是好矩阵，你能帮帮她吗？接下来的n行，每行输入一个仅包含大写字母的长度为m的字符串。第一行输入两个整数n,m，代表矩阵的行数和列数。左下角的存在两个相邻的字母相同，因此不合法。左上角的子矩阵出现了’D’，因此不合法。右下角的子矩阵里没有’C’，因此不合法。解法：纯模拟，被恶心到了。输出一个整数表示答案。有4个3*3的子矩阵。

文章共1,341字 · 阅读需要大约5分钟

一键AI生成摘要，助你高效阅读

问答

weixin_43739821

1363人浏览 · 2024-02-26 16:10:18

weixin_43739821 · 2024-02-26 16:10:18 发布

小美定义一个矩阵是好矩阵，当且仅当该矩阵满足：

矩阵仅由’A’、‘B’、'C’三种字符组成。且三种字符都出现过。
矩阵相邻的字符都不相等。

现在给定一个n∗m的矩阵，小美想知道有多少个3*3的子矩阵是好矩阵，你能帮帮她吗？

输入描述：
第一行输入两个整数n,m，代表矩阵的行数和列数。
接下来的n行，每行输入一个仅包含大写字母的长度为m的字符串。
1<=n,m<=1000

输出描述：
输出一个整数表示答案。

示例1

输入例子：
4 4
DABC
ABAB
BABA
BBAB

输出例子：
1

例子说明：
有4个3*3的子矩阵。
左上角的子矩阵出现了’D’，因此不合法。
右上角的是好矩阵。
左下角的存在两个相邻的字母相同，因此不合法。
右下角的子矩阵里没有’C’，因此不合法。

解法：纯模拟，被恶心到了。

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        char[][] matrix = new char[n][m];
        for (int i = 0; i < n; i++) {
            matrix[i] = scanner.next().toCharArray();//小trick
        }
        int count = 0;
        for (int i = 0; i < n - 2; i++) {
            for (int j = 0; j < m - 2; j++) {
                if (isGoodMatrix(matrix, i, j)) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }

    private static boolean isGoodMatrix(char[][] matrix, int x, int y) {
        int[] count = new int[26];
        for (int i = x; i < x + 3; i++) {
            for (int j = y; j < y + 3; j++) {
                if (matrix[i][j] < 'A' || matrix[i][j] > 'C') {
                    return false;
                }
                count[matrix[i][j] - 'A']++;
                if (i > x && matrix[i][j] == matrix[i - 1][j]) {
                    return false;
                }
                if (j > y && matrix[i][j] == matrix[i][j - 1]) {
                    return false;
                }
            }
        }
        return count[0] > 0 && count[1] > 0 && count[2] > 0;
    }
}