刷题笔记合集🔗

最大相连男生数-学生方阵

问题描述

学校组织了一项活动，将学生排成一个矩形方阵。现在需要在这个矩形方阵中找到最大的位置相连的男生数量。相连位置可以是在一条直线上，方向可以是水平的、垂直的、成对角线的或者呈反对角线的。

输入格式

第一行包含两个正整数 和 ，分别表示矩阵的行数和列数，用逗号分隔。

接下来的 行每行包含 个字符，表示矩阵元素，字符间用逗号分隔。其中 'M' 表示男生，'F' 表示女生。

输出格式

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

样例输入1

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

样例输出1

3

样例输入2

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

样例输出2

4

样例解释

数据范围

• 
• 学生总数不会超过 10000

题解

模拟

解题思路如下：

1. 遍历矩阵中的每一个点。
2. 对于每个点，如果是男生('M')，则分别计算四个方向（水平、垂直、正对角线、反对角线）的连续男生数量。
3. 在计算过程中，为了避免重复计算，可以只计算向右、向下、右下和左下四个方向。
4. 维护一个全局的最大值，记录找到的最长男生序列长度。

为了优化性能，可以采用以下策略：

1. 当遇到一个男生时，先检查其左上、上方和左方是否为男生。如果是，则说明这个方向的计算已经在之前的遍历中完成，可以跳过。
2. 只有当前方向没有被计算过时，才进行计算。

参考代码

• Python

def find_max_boys(matrix):
    """
    寻找矩阵中最长的相连男生序列
    :param matrix: 输入的矩阵
    :return: 最长的相连男生序列长度
    """
    rows, cols = len(matrix), len(matrix[0])
    max_count = 0

    def count_boys(i, j, di, dj):
        """
        计算从(i,j)开始，沿着(di,dj)方向的连续男生数量
        """
        count = 0
        while 0 <= i < rows and 0 <= j < cols and matrix[i][j] == 'M':
            count += 1
            i += di
            j += dj
        return count

    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == 'M':
                # 检查左上、上方和左方，如果是'M'则跳过该方向
                directions = [(0, 1), (1, 0), (1, 1), (1, -1)]
                if i > 0 and j > 0 and matrix[i-1][j-1] == 'M':
                    directions.remove((1, 1))
                if i > 0 and matrix[i-1][j] == 'M':
                    directions.remove((1, 0))
                if j > 0 and matrix[i][j-1] == 'M':
                    directions.remove((0, 1))

                for di, dj in directions:
                    max_count = max(max_count, count_boys(i, j, di, dj))

    return max_count

# 读取输入
n, m = map(int, input().split(','))
matrix = [input().split(',') for _ in range(n)]

# 计算并输出结果
print(find_max_boys(matrix))

• C

#include <stdio.h>
#include <string.h>

#define MAX_N 100
#define MAX_M 100

char matrix[MAX_N][MAX_M];
int n, m;

int count_boys(int i, int j, int di, int dj) {
    int count = 0;
    while (i >= 0 && i < n && j >= 0 && j < m && matrix[i][j] == 'M') {
        count++;
        i += di;
        j += dj;
    }
    return count;
}

int find_max_boys() {
    int max_count = 0;
    int directions[4][2] = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 'M') {
                for (int k = 0; k < 4; k++) {
                    int di = directions[k][0], dj = directions[k][1];
                    if ((i > 0 && j > 0 && matrix[i-1][j-1] == 'M' && di == 1 && dj == 1) ||
                        (i > 0 && matrix[i-1][j] == 'M' && di == 1 && dj == 0) ||
                        (j > 0 && matrix[i][j-1] == 'M' && di == 0 && dj == 1)) {
                        continue;
                    }
                    int count = count_boys(i, j, di, dj);
                    if (count > max_count) {
                        max_count = count;
                    }
                }
            }
        }
    }
    return max_count;
}

int main() {
    scanf("%d,%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf(" %c,", &matrix[i][j]);
        }
    }
    printf("%d\n", find_max_boys());
    return 0;
}

• Javascript

function findMaxBo