题目描述与示例

题目描述

学校组织活动，将学生排成一个矩形方阵。

请在矩形方阵中找到最大的位置相连的男生数量。

这个相连位置在一个直线上，方向可以是水平的、垂直的、成对角线的或者反对角线的。

注：学生个数不会超过 10000。

题目练习网址：https://www.algomooc.com/problem/P2519

输入描述

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

输出描述

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

示例

输入

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

输出

3

解题思路

本题题意并不难理解，其实就是考虑每一个M的横向、纵向、对角线、反对角线各自有多少连续的M。

M表示male，F表示female，这一点在题目中没有明说，但是容易想到。

对于某一段连续的M，很显然我们考虑最边上M往另一边延申，考虑中间的M往两边延申，最后计算得到的连续的M的个数是一样的。

譬如

暂时无法在飞书文档外展示此内容

那么从边上的M往另一边计算

暂时无法在飞书文档外展示此内容

和从中间的M往两边计算

暂时无法在飞书文档外展示此内容

能够得到的连续的M的个数是一样的。

那么哪一种更加方便我们计算呢？

显然是前一种。

假设我们能够通过前一种方式，计算得到某段连续的M的个数，那么后一种方式的计算是冗余的、无意义的计算。

因此我们应该考虑，尽可能用前一种简单方式来计算连续的M，且需要避免漏算。

如何做到这一点呢？考虑一个例子。

如果我们从上到下，从左到右地考虑每一个矩阵中的字符串（即顺序遍历），容易发现，先遇到的M，一定是

• 横向的连续的M中最左边的那个
• 纵向的连续的M中最上边的那个
• 对角线的连续的M中最左上角的那个
• 反对角线的连续的M中最右上角的那个

暂时无法在飞书文档外展示此内容

显然，这个M对于四种方向而言，都是连续的M中，最边上的那个M（深红色的M）。

所以，如果我们从上到下，从左到右地顺序遍历每一个元素的话，我们率先遇到那个M一定是满足前一种方式的计算思路的。

整体代码框架如下

# 从上到下，从左到右顺序枚举矩阵中的每一个元素
for i in range(n):
    for j in range(m):
        # 考虑横向
        pass
        
        # 考虑纵向
        pass
        
        # 考虑主对角线
        pass
        
        # 考虑反对角线
        pass

那么，我们又应该如何避免对位于其他位置的M（浅红色的M）进行重复计算，且不漏算呢？

以考虑横向方向为例，我们可以设计一个大小和原矩阵完全一样的n*m的检查矩阵check1。

check1中的元素为0或1。初始化均为0。

• check1[i][j] = 0表示某个位置(i, j)尚未被考虑包含在某段连续的横向的M中
• check1[i][j] = 1表示某个位置(i, j)已经被考虑包含在某段连续的横向的M中了

对应的代码如下

check1 = [[0] * m for _ in range(n)]

# 从上到下，从左到右顺序枚举矩阵中的每一个元素
for i in range(n):
    for j in range(m):
        # 如果某个M尚未被考虑包含在某段连续的【横向】的M中
        # 则【向右】考虑这整段横向的M
        if mat[i][j] == "M" and check1[i][j] == 0:
            # (x,y)为横向移动时的坐标
            # (dx,dy)为横向移动的坐标偏差
            x, y, dx, dy = i, j, 0, 1
            # 当x和y不越界，且mat[x][y]仍为M时，进行横向移动的考虑
            # 修改check[x][y]为已检查过，且(x,y)修改
            while 0 <= x < n and 0 <= y < m and mat[x][y] == "M" and check1[x][y] == 0:
                check1[x][y] = 1
                x += dx
                y += dy
            # 退出while循环后，此段横向的连续的M的长度为y-j，更新答案
            ans = max(ans, y-j)

而对应的其他三个方向，也可以直接如法炮制了。

这样我们就可以使用4个不同的check矩阵，来判断某一个位置的M是否已经在某个方向上计算过，来避免发生无用的重复计算了。

这样就完成了本题分类写法（较为臃肿）。

PS：四个方向的check矩阵，均仅由0或1构成。思考以前讲过的状态压缩技巧，你能否仅用一个其中元素范围为整数0-15的check矩阵来表示所有状态？题解的最后提供了状态压缩写法的代码。

代码

代码一：分类写法

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频


# 输入矩阵的行数n，列数m
n, m = map(int, input().split(","))

# 初始化二维矩阵
mat = list()
# 循环n行，输入矩阵
for _ in range(n):
    mat.append(input().split(","))


# 初始化答案变量，指的是最长连续男生数量
ans = 0

# 四个检查矩阵，分别表示横向、纵向、对角线、反对角线方向上
# 某一个M是否已经在某段连续的M中被考虑过
check1 = [[0] * m for _ in range(n)]
check2 = [[0] * m for _ in range(n)]
check3 = [[0] * m for _ in range(n)]
check4 = [[0] * m for _ in range(n)]


# 从上到下，从左到右顺序枚举矩阵中的每一个元素
for i in range(n):
    for j in range(m):
        # 如果某个M尚未被考虑包含在某段连续的【横向】的M中
        # 则【向右】考虑这整段横向的M
        if mat[i][j] == "M" and check1[i][j] == 0:
            # (x,y)为横向移动时的坐标
            # (dx,dy)为横向移动的坐标偏差
            x, y, dx, dy = i, j, 0, 1
            # 当x和y不越界，且mat[x][y]仍为M时，进行横向移动的考虑
            # 修改check1[x][y]为已检查过，且(x,y)修改
            while 0 <= x < n and 0 <= y < m and mat[x][y] == "M":
                check1[x][y] = 1
                x += dx
                y += dy
            # 退出while循环后，此段横向的连续的M的长度为y-j，更新答案
            ans = max(ans, y-j)

        # 如果某个M尚未被考虑包含在某段连续的【纵向】的M中
        # 则【向下】考虑这整段纵向的M
        if mat[i][j] == "M" and check2[i][j] == 0:
            # (x,y)为纵向移动时的坐标
            # (dx,dy)为纵向移动的坐标偏差
            x, y, dx, dy = i, j, 1, 0
            # 当x和y不越界，且mat[x][y]仍为M时，进行纵向移动的考虑
            # 修改check2[x][y]为已检查过，且(x,y)修改
            while 0 <= x < n and 0 <= y < m and mat[x][y] == "M":
                check2[x][y] = 1
                x += dx
                y += dy
            # 退出while循环后，此段纵向的连续的M的长度为x-i，更新答案
            ans = max(ans, x-i)

        # 如果某个M尚未被考虑包含在某段连续的【对角线方向】的M中
        # 则【向右下】考虑这整段对角线方向的M
        if mat[i][j] == "M" and check3[i][j] == 0:
            # (x,y)为对角线方向移动时的坐标
            # (dx,dy)为对角线方向移动的坐标偏差
            x, y, dx, dy = i, j, 1, 1
            # 当x和y不越界，且mat[x][y]仍为M时，进行对角线方向移动的考虑
            # 修改check3[x][y]为已检查过，且(x,y)修改
            while 0 <= x < n and 0 <= y < m and mat[x][y] == "M":
                check3[x][y] = 1
                x += dx
                y += dy
            # 退出while循环后，此段对角线方向的连续的M的长度为x-i，更新答案
            ans = max(ans, x-i)


        # 如果某个M尚未被考虑包含在某段连续的【反对角线方向】的M中
        # 则【向左下】考虑这整段反对角线方向的M
        if mat[i][j] == "M" and check4[i][j] == 0:
            # (x,y)为反对角线方向移动时的坐标
            # (dx,dy)为反对角线方向移动的坐标偏差
            x, y, dx, dy = i, j, 1, -1
            # 当x和y不越界，且mat[x][y]仍为M时，进行反对角线方向移动的考虑
            # 修改check4[x][y]为已检查过，且(x,y)修改
            while 0 <= x < n and 0 <= y < m and mat[x][y] == "M":
                check4[x][y] = 1
                x += dx
                y += dy
            # 退出while循环后，此段反对角线方向的连续的M的长度为x-i，更新答案
            ans = max(ans, x-i)

print(ans)

Java

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入矩阵的行数n，列数m
        String[] input = scanner.nextLine().split(",");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        // 初始化二维矩阵
        String[][] mat = new String[n][m];
        // 循环n行，输入矩阵
        for (int i = 0; i < n; i++) {
            mat[i] = scanner.nextLine().split(",");
        }

        // 初始化答案变量，指的是最长连续男生数量
        int ans = 0;

        // 四个检查矩阵，分别表示横向、纵向、对角线、反对角线方向上
        // 某一个M是否已经在某段连续的M中被考虑过
        boolean[][] check1 = new boolean[n][m];
        boolean[][] check2 = new boolean[n][m];
        boolean[][] check3 = new boolean[n][m];
        boolean[][] check4 = new boolean[n][m];

        // 从上到下，从左到右顺序枚举矩阵中的每一个元素
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 如果某个M尚未被考虑包含在某段连续的【横向】的M中
                // 则【向右】考虑这整段横向的M
                if (mat[i][j].equals("M") && !check1[i][j]) {
                    // (x,y)为横向移动时的坐标
                    // (dx,dy)为横向移动的坐标偏差
                    int x = i, y = j, dx = 0, dy = 1;
                    // 当x和y不越界，且mat[x][y]仍为M时，进行横向移动的考虑
                    // 修改check1[x][y]为已检查过，且(x,y)修改
                    while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y].equals("M")) {
                        check1[x][y] = true;
                        y += dy;
                    }
                    // 退出while循环后，此段横向的连续的M的长度为y-j，更新答案
                    ans = Math.max(ans, y - j);
                }

                // 如果某个M尚未被考虑包含在某段连续的【纵向】的M中
                // 则【向下】考虑这整段纵向的M
                if (mat[i][j].equals("M") && !check2[i][j]) {
                    // (x,y)为纵向移动时的坐标
                    // (dx,dy)为纵向移动的坐标偏差
                    int x = i, y = j, dx = 1, dy = 0;
                    // 当x和y不越界，且mat[x][y]仍为M时，进行纵向移动的考虑
                    // 修改check2[x][y]为已检查过，且(x,y)修改
                    while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y].equals("M")) {
                        check2[x][y] = true;
                        x += dx;
                    }
                    // 退出while循环后，此段纵向的连续的M的长度为x-i，更新答案
                    ans = Math.max(ans, x - i);
                }

                // 如果某个M尚未被考虑包含在某段连续的【对角线方向】的M中
                // 则【向右下】考虑这整段对角线方向的M
                if (mat[i][j].equals("M") && !check3[i][j]) {
                    // (x,y)为对角线方向移动时的坐标
                    // (dx,dy)为对角线方向移动的坐标偏差
                    int x = i, y = j, dx = 1, dy = 1;
                    // 当x和y不越界，且mat[x][y]仍为M时，进行对角线方向移动的考虑
                    // 修改check3[x][y]为已检查过，且(x,y)修改
                    while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y].equals("M")) {
                        check3[x][y] = true;
                        x += dx;
                        y += dy;
                    }
                    // 退出while循环后，此段对角线方向的连续的M的长度为x-i，更新答案
                    ans = Math.max(ans, x - i);
                }

                // 如果某个M尚未被考虑包含在某段连续的【反对角线方向】的M中
                // 则【向左下】考虑这整段反对角线方向的M
                if (mat[i][j].equals("M") && !check4[i][j]) {
                    // (x,y)为反对角线方向移动时的坐标
                    // (dx,dy)为反对角线方向移动的坐标偏差
                    int x = i, y = j, dx = 1, dy = -1;
                    // 当x和y不越界，且mat[x][y]仍为M时，进行反对角线方向移动的考虑
                    // 修改check4[x][y]为已检查过，且(x,y)修改
                    while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y].equals("M")) {
                        check4[x][y] = true;
                        x += dx;
                        y += dy;
                    }
                    // 退出while循环后，此段反对角线方向的连续的M的长度为x-i，更新答案
                    ans = Math.max(ans, x - i);
                }
            }
        }

        // 输出答案
        System.out.println(ans);

        scanner.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 输入矩阵的行数n，列数m
    string input;
    getline(cin, input);
    int n, m;
    sscanf(input.c_str(), "%d,%d", &n, &m);

    // 初始化二维矩阵
    vector<vector<string>> mat(n, vector<string>(m));
    // 循环n行，输入矩阵
    for (int i = 0; i < n; i++) {
        string line;
        getline(cin, line);
        size_t pos = 0;
        for (int j = 0; j < m; j++) {
            size_t next_pos = line.find(',', pos);
            mat[i][j] = line.substr(pos, next_pos - pos);
            pos = next_pos + 1;
        }
    }

    // 初始化答案变量，指的是最长连续男生数量
    int ans = 0;

    // 四个检查矩阵，分别表示横向、纵向、对角线、反对角线方向上
    // 某一个M是否已经在某段连续的M中被考虑过
    vector<vector<bool>> check1(n, vector<bool>(m, false));
    vector<vector<bool>> check2(n, vector<bool>(m, false));
    vector<vector<bool>> check3(n, vector<bool>(m, false));
    vector<vector<bool>> check4(n, vector<bool>(m, false));

    // 从上到下，从左到右顺序枚举矩阵中的每一个元素
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 如果某个M尚未被考虑包含在某段连续的【横向】的M中
            // 则【向右】考虑这整段横向的M
            if (mat[i][j] == "M" && !check1[i][j]) {
                // (x,y)为横向移动时的坐标
                // (dx,dy)为横向移动的坐标偏差
                int x = i, y = j, dx = 0, dy = 1;
                // 当x和y不越界，且mat[x][y]仍为M时，进行横向移动的考虑
                // 修改check1[x][y]为已检查过，且(x,y)修改
                while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == "M") {
                    check1[x][y] = true;
                    y += dy;
                }
                // 退出while循环后，此段横向的连续的M的长度为y-j，更新答案
                ans = max(ans, y - j);
            }

            // 如果某个M尚未被考虑包含在某段连续的【纵向】的M中
            // 则【向下】考虑这整段纵向的M
            if (mat[i][j] == "M" && !check2[i][j]) {
                // (x,y)为纵向移动时的坐标
                // (dx,dy)为纵向移动的坐标偏差
                int x = i, y = j, dx = 1, dy = 0;
                // 当x和y不越界，且mat[x][y]仍为M时，进行纵向移动的考虑
                // 修改check2[x][y]为已检查过，且(x,y)修改
                while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == "M") {
                    check2[x][y] = true;
                    x += dx;
                }
                // 退出while循环后，此段纵向的连续的M的长度为x-i，更新答案
                ans = max(ans, x - i);
            }

            // 如果某个M尚未被考虑包含在某段连续的【对角线方向】的M中
            // 则【向右下】考虑这整段对角线方向的M
            if (mat[i][j] == "M" && !check3[i][j]) {
                // (x,y)为对角线方向移动时的坐标
                // (dx,dy)为对角线方向移动的坐标偏差
                int x = i, y = j, dx = 1, dy = 1;
                // 当x和y不越界，且mat[x][y]仍为M时，进行对角线方向移动的考虑
                // 修改check3[x][y]为已检查过，且(x,y)修改
                while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == "M") {
                    check3[x][y] = true;
                    x += dx;
                    y += dy;
                }
                // 退出while循环后，此段对角线方向的连续的M的长度为x-i，更新答案
                ans = max(ans, x - i);
            }

            // 如果某个M尚未被考虑包含在某段连续的【反对角线方向】的M中
            // 则【向左下】考虑这整段反对角线方向的M
            if (mat[i][j] == "M" && !check4[i][j]) {
                // (x,y)为反对角线方向移动时的坐标
                // (dx,dy)为反对角线方向移动的坐标偏差
                int x = i, y = j, dx = 1, dy = -1;
                // 当x和y不越界，且mat[x][y]仍为M时，进行反对角线方向移动的考虑
                // 修改check4[x][y]为已检查过，且(x,y)修改
                while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == "M") {
                    check4[x][y] = true;
                    x += dx;
                    y += dy;
                }
                // 退出while循环后，此段反对角线方向的连续的M的长度为x-i，更新答案
                ans = max(ans, x - i);
            }
        }
    }

    // 输出答案
    cout << ans << endl;

    return 0;
}

C

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

// 定义矩阵的最大行列数
#define MAX 100

int main() {
    int n, m;
    // 输入矩阵的行数n和列数m
    scanf("%d,%d", &n, &m);

    // 初始化二维矩阵
    char mat[MAX][MAX];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf(" %c,", &mat[i][j]);  // 用逗号分隔读取输入
        }
    }

    // 初始化答案变量，指的是最长连续男生数量
    int ans = 0;

    // 初始化四个检查矩阵
    // check1、check2、check3、check4分别对应横向、纵向、对角线方向、反对角线方向的检查状态
    int check1[MAX][MAX], check2[MAX][MAX], check3[MAX][MAX], check4[MAX][MAX];
    memset(check1, 0, sizeof(check1));
    memset(check2, 0, sizeof(check2));
    memset(check3, 0, sizeof(check3));
    memset(check4, 0, sizeof(check4));

    // 从上到下，从左到右顺序枚举矩阵中的每一个元素
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 【横向】向右
            if (mat[i][j] == 'M' && check1[i][j] == 0) {
                int x = i, y = j, dx = 0, dy = 1, length = 0;
                while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == 'M') {
                    check1[x][y] = 1;
                    y += dy;
                    length++;
                }
                if (length > ans) ans = length;
            }

            // 【纵向】向下
            if (mat[i][j] == 'M' && check2[i][j] == 0) {
                int x = i, y = j, dx = 1, dy = 0, length = 0;
                while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == 'M') {
                    check2[x][y] = 1;
                    x += dx;
                    length++;
                }
                if (length > ans) ans = length;
            }

            // 【对角线】向右下
            if (mat[i][j] == 'M' && check3[i][j] == 0) {
                int x = i, y = j, dx = 1, dy = 1, length = 0;
                while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == 'M') {
                    check3[x][y] = 1;
                    x += dx;
                    y += dy;
                    length++;
                }
                if (length > ans) ans = length;
            }

            // 【反对角线】向左下
            if (mat[i][j] == 'M' && check4[i][j] == 0) {
                int x = i, y = j, dx = 1, dy = -1, length = 0;
                while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == 'M') {
                    check4[x][y] = 1;
                    x += dx;
                    y += dy;
                    length++;
                }
                if (length > ans) ans = length;
            }
        }
    }

    // 输出答案
    printf("%d\n", ans);

    return 0;
}

Node JavaScript

const readline = require("readline");

// 输入读取
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 主函数
function main(input) {
    const lines = input.split("\n");
    const [n, m] = lines[0].split(",").map(Number);
    const mat = lines.slice(1).map(row => row.split(","));

    // 初始化答案变量
    let ans = 0;

    // 初始化检查矩阵
    const check1 = Array.from({ length: n }, () => Array(m).fill(0));
    const check2 = Array.from({ length: n }, () => Array(m).fill(0));
    const check3 = Array.from({ length: n }, () => Array(m).fill(0));
    const check4 = Array.from({ length: n }, () => Array(m).fill(0));

    // 遍历矩阵
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            // 横向
            if (mat[i][j] === "M" && check1[i][j] === 0) {
                let x = i, y = j, dx = 0, dy = 1, length = 0;
                while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] === "M") {
                    check1[x][y] = 1;
                    y += dy;
                    length++;
                }
                ans = Math.max(ans, length);
            }

            // 纵向
            if (mat[i][j] === "M" && check2[i][j] === 0) {
                let x = i, y = j, dx = 1, dy = 0, length = 0;
                while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] === "M") {
                    check2[x][y] = 1;
                    x += dx;
                    length++;
                }
                ans = Math.max(ans, length);
            }

            // 对角线
            if (mat[i][j] === "M" && check3[i][j] === 0) {
                let x = i, y = j, dx = 1, dy = 1, length = 0;
                while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] === "M") {
                    check3[x][y] = 1;
                    x += dx;
                    y += dy;
                    length++;
                }
                ans = Math.max(ans, length);
            }

            // 反对角线
            if (mat[i][j] === "M" && check4[i][j] === 0) {
                let x = i, y = j, dx = 1, dy = -1, length = 0;
                while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] === "M") {
                    check4[x][y] = 1;
                    x += dx;
                    y += dy;
                    length++;
                }
                ans = Math.max(ans, length);
            }
        }
    }

    console.log(ans);
}

// 读取所有输入
let input = "";
rl.on("line", (line) => {
    input += line + "\n";
});
rl.on("close", () => {
    main(input.trim());
});

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "strconv"
        "strings"
)

func main() {
        // 输入读取
        scanner := bufio.NewScanner(os.Stdin)
        scanner.Scan()
        firstLine := scanner.Text()
        dimensions := strings.Split(firstLine, ",")
        n, _ := strconv.Atoi(dimensions[0])
        m, _ := strconv.Atoi(dimensions[1])

        // 初始化矩阵
        mat := make([][]string, n)
        for i := 0; i < n; i++ {
                scanner.Scan()
                row := strings.Split(scanner.Text(), ",")
                mat[i] = row
        }

        // 初始化答案变量
        ans := 0

        // 初始化检查矩阵
        check1 := make([][]int, n)
        check2 := make([][]int, n)
        check3 := make([][]int, n)
        check4 := make([][]int, n)
        for i := 0; i < n; i++ {
                check1[i] = make([]int, m)
                check2[i] = make([]int, m)
                check3[i] = make([]int, m)
                check4[i] = make([]int, m)
        }

        // 遍历矩阵
        for i := 0; i < n; i++ {
                for j := 0; j < m; j++ {
                        // 横向
                        if mat[i][j] == "M" && check1[i][j] == 0 {
                                x, y, _, dy, length := i, j, 0, 1, 0
                                for x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == "M" {
                                        check1[x][y] = 1
                                        y += dy
                                        length++
                                }
                                if length > ans {
                                        ans = length
                                }
                        }

                        // 纵向
                        if mat[i][j] == "M" && check2[i][j] == 0 {
                                x, y, dx, _, length := i, j, 1, 0, 0
                                for x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == "M" {
                                        check2[x][y] = 1
                                        x += dx
                                        length++
                                }
                                if length > ans {
                                        ans = length
                                }
                        }

                        // 对角线
                        if mat[i][j] == "M" && check3[i][j] == 0 {
                                x, y, dx, dy, length := i, j, 1, 1, 0
                                for x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == "M" {
                                        check3[x][y] = 1
                                        x += dx
                                        y += dy
                                        length++
                                }
                                if length > ans {
                                        ans = length
                                }
                        }

                        // 反对角线
                        if mat[i][j] == "M" && check4[i][j] == 0 {
                                x, y, dx, dy, length := i, j, 1, -1, 0
                                for x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == "M" {
                                        check4[x][y] = 1
                                        x += dx
                                        y += dy
                                        length++
                                }
                                if length > ans {
                                        ans = length
                                }
                        }
                }
        }

        // 输出答案
        fmt.Println(ans)
}

代码二：合并写法

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频


# 四个方向的偏移变量
# DIRECTIONS[0]、DIRECTIONS[1]、DIRECTIONS[2]、DIRECTIONS[3]分别表示
# 横向向右、纵向向下、主对角线方向向右下、反对角线反向向左下的4个方向
DIRECTIONS = [(0, 1), (1, 0), (1, 1), (1, -1)]

# 输入矩阵的行数n，列数m
n, m = map(int, input().split(","))

# 初始化二维矩阵
mat = list()
# 循环n行，输入矩阵
for _ in range(n):
    mat.append(input().split(","))


# 初始化答案变量，指的是最长连续男生数量
ans = 0

# 四个检查矩阵，check[0]、check[1]、check[2]、check[3]
# 分别表示横向、纵向、对角线、反对角线方向上
# 某一个M是否已经在某段连续的M中被考虑过
check = [[[0] * m for _ in range(n)] for __ in range(4)]


# 从上到下，从左到右顺序枚举矩阵中的每一个元素
for i in range(n):
    for j in range(m):
        # 考虑横向、纵向、主对角线方向、反对角线方向4个方向
        for k in range(4):
            # 如果某个M尚未被考虑包含在某段连续的的M中
            # 则考虑这段M
            if mat[i][j] == "M" and check[k][i][j] == 0:
                # (x,y)为移动时的坐标
                # (dx,dy)为移动的坐标偏差
                x, y = i, j
                dx, dy = DIRECTIONS[k]
                # 当x和y不越界，且mat[x][y]仍为M时，进行进一步移动的考虑
                # 修改check[k][x][y]为已检查过，且(x,y)修改
                while 0 <= x < n and 0 <= y < m and mat[x][y] == "M":
                    check[k][x][y] = 1
                    x += dx
                    y += dy
                # 退出while循环后，此段横向的连续的M的长度为x-i或y-j（取其中较大值），更新答案
                ans = max(ans, max(x-i, y-j))

print(ans)

Java

import java.util.Scanner;

public class Main {

    // 四个方向的偏移变量
    // DIRECTIONS[0]、DIRECTIONS[1]、DIRECTIONS[2]、DIRECTIONS[3]分别表示
    // 横向向右、纵向向下、主对角线方向向右下、反对角线方向向左下的4个方向
    private static final int[][] DIRECTIONS = {
            {0, 1},   // 横向向右
            {1, 0},   // 纵向向下
            {1, 1},   // 主对角线方向向右下
            {1, -1}   // 反对角线方向向左下
    };

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入矩阵的行数n，列数m
        String[] input = scanner.nextLine().split(",");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        // 初始化二维矩阵
        String[][] mat = new String[n][m];
        // 循环n行，输入矩阵
        for (int i = 0; i < n; i++) {
            mat[i] = scanner.nextLine().split(",");
        }

        // 初始化答案变量，指的是最长连续男生数量
        int ans = 0;

        // 四个检查矩阵，check[0]、check[1]、check[2]、check[3]
        // 分别表示横向、纵向、对角线、反对角线方向上
        // 某一个M是否已经在某段连续的M中被考虑过
        boolean[][][] check = new boolean[4][n][m];

        // 从上到下，从左到右顺序枚举矩阵中的每一个元素
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 考虑横向、纵向、主对角线方向、反对角线方向4个方向
                for (int k = 0; k < 4; k++) {
                    // 如果某个M尚未被考虑包含在某段连续的的M中
                    // 则考虑这段M
                    if (mat[i][j].equals("M") && !check[k][i][j]) {
                        // (x,y)为移动时的坐标
                        // (dx,dy)为移动的坐标偏差
                        int x = i, y = j;
                        int dx = DIRECTIONS[k][0], dy = DIRECTIONS[k][1];
                        // 当x和y不越界，且mat[x][y]仍为M时，进行进一步移动的考虑
                        // 修改check[k][x][y]为已检查过，且(x,y)修改
                        while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y].equals("M")) {
                            check[k][x][y] = true;
                            x += dx;
                            y += dy;
                        }
                        // 退出while循环后，此段横向的连续的M的长度为x-i或y-j（取其中较大值），更新答案
                        ans = Math.max(ans, Math.max(x - i, y - j));
                    }
                }
            }
        }

        // 输出答案
        System.out.println(ans);

        scanner.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 四个方向的偏移变量
// DIRECTIONS[0]、DIRECTIONS[1]、DIRECTIONS[2]、DIRECTIONS[3]分别表示
// 横向向右、纵向向下、主对角线方向向右下、反对角线方向向左下的4个方向
const int DIRECTIONS[4][2] = {
    {0, 1},   // 横向向右
    {1, 0},   // 纵向向下
    {1, 1},   // 主对角线方向向右下
    {1, -1}   // 反对角线方向向左下
};

int main() {
    // 输入矩阵的行数n，列数m
    int n, m;
    char comma;
    cin >> n >> comma >> m;
    cin.ignore(); // 忽略换行符

    // 初始化二维矩阵
    vector<vector<string>> mat(n, vector<string>(m));
    // 循环n行，输入矩阵
    for (int i = 0; i < n; i++) {
        string line;
        getline(cin, line);
        size_t pos = 0;
        for (int j = 0; j < m; j++) {
            size_t next_pos = line.find(',', pos);
            mat[i][j] = line.substr(pos, next_pos - pos);
            pos = next_pos + 1;
        }
    }

    // 初始化答案变量，指的是最长连续男生数量
    int ans = 0;

    // 四个检查矩阵，check[0]、check[1]、check[2]、check[3]
    // 分别表示横向、纵向、对角线、反对角线方向上
    // 某一个M是否已经在某段连续的M中被考虑过
    vector<vector<vector<bool>>> check(4, vector<vector<bool>>(n, vector<bool>(m, false)));

    // 从上到下，从左到右顺序枚举矩阵中的每一个元素
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 考虑横向、纵向、主对角线方向、反对角线方向4个方向
            for (int k = 0; k < 4; k++) {
                // 如果某个M尚未被考虑包含在某段连续的的M中
                // 则考虑这段M
                if (mat[i][j] == "M" && !check[k][i][j]) {
                    // (x,y)为移动时的坐标
                    // (dx,dy)为移动的坐标偏差
                    int x = i, y = j;
                    int dx = DIRECTIONS[k][0], dy = DIRECTIONS[k][1];
                    // 当x和y不越界，且mat[x][y]仍为M时，进行进一步移动的考虑
                    // 修改check[k][x][y]为已检查过，且(x,y)修改
                    while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == "M") {
                        check[k][x][y] = true;
                        x += dx;
                        y += dy;
                    }
                    // 退出while循环后，此段横向的连续的M的长度为x-i或y-j（取其中较大值），更新答案
                    ans = max(ans, max(x - i, y - j));
                }
            }
        }
    }

    // 输出答案
    cout << ans << endl;

    return 0;
}

C

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

// 定义四个方向的偏移变量
// DIRECTIONS[0]、DIRECTIONS[1]、DIRECTIONS[2]、DIRECTIONS[3]分别表示
// 横向向右、纵向向下、主对角线方向向右下、反对角线方向向左下的4个方向
const int DIRECTIONS[4][2] = {
    {0, 1},  // 横向
    {1, 0},  // 纵向
    {1, 1},  // 主对角线
    {1, -1}  // 反对角线
};

int main() {
    int n, m;
    // 输入矩阵的行数n，列数m
    scanf("%d,%d", &n, &m);

    // 初始化二维矩阵
    char mat[n][m + 1];  // +1是为了处理输入时的逗号分隔
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf(" %c,", &mat[i][j]);  // 每个元素以逗号分隔输入
        }
    }

    // 初始化答案变量，指的是最长连续男生数量
    int ans = 0;

    // 四个检查矩阵，分别对应4个方向
    // 检查某个"M"是否已经被考虑包含在某段连续的"M"中
    int check[4][n][m];
    memset(check, 0, sizeof(check));  // 初始化为0，表示未被检查过

    // 从上到下，从左到右顺序枚举矩阵中的每一个元素
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 考虑横向、纵向、主对角线方向、反对角线方向4个方向
            for (int k = 0; k < 4; k++) {
                // 如果某个"M"尚未被考虑包含在某段连续的"M"中
                // 则开始考虑这段"M"
                if (mat[i][j] == 'M' && check[k][i][j] == 0) {
                    int x = i, y = j;
                    int dx = DIRECTIONS[k][0], dy = DIRECTIONS[k][1];
                    int length = 0;

                    // 当x和y不越界，且mat[x][y]仍为"M"时，继续检查
                    while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == 'M') {
                        // 标记此位置为已检查
                        check[k][x][y] = 1;
                        x += dx;
                        y += dy;
                        length++;
                    }

                    // 更新答案
                    if (length > ans) {
                        ans = length;
                    }
                }
            }
        }
    }

    // 输出答案
    printf("%d\n", ans);

    return 0;
}

Node JavaScript

const readline = require("readline");

// 定义四个方向的偏移变量
// DIRECTIONS[0]、DIRECTIONS[1]、DIRECTIONS[2]、DIRECTIONS[3]分别表示
// 横向向右、纵向向下、主对角线方向向右下、反对角线反向向左下的4个方向
const DIRECTIONS = [
    [0, 1],  // 横向
    [1, 0],  // 纵向
    [1, 1],  // 主对角线
    [1, -1], // 反对角线
];

function main() {
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout,
    });

    let inputLines = [];
    rl.on("line", (line) => {
        inputLines.push(line);
    });

    rl.on("close", () => {
        // 读取矩阵的行数和列数
        const [n, m] = inputLines[0].split(",").map(Number);

        // 初始化二维矩阵
        const mat = [];
        for (let i = 1; i <= n; i++) {
            mat.push(inputLines[i].split(","));
        }

        // 初始化答案变量，指的是最长连续男生数量
        let ans = 0;

        // 初始化四个检查矩阵
        const check = Array.from({ length: 4 }, () =>
            Array.from({ length: n }, () => Array(m).fill(0))
        );

        // 从上到下，从左到右顺序枚举矩阵中的每一个元素
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < m; j++) {
                // 考虑横向、纵向、主对角线方向、反对角线方向4个方向
                for (let k = 0; k < 4; k++) {
                    // 如果某个M尚未被考虑包含在某段连续的的M中
                    // 则考虑这段M
                    if (mat[i][j] === "M" && check[k][i][j] === 0) {
                        let x = i, y = j;
                        const [dx, dy] = DIRECTIONS[k];
                        let length = 0;

                        // 当x和y不越界，且mat[x][y]仍为M时，进行进一步移动的考虑
                        while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] === "M") {
                            check[k][x][y] = 1;
                            x += dx;
                            y += dy;
                            length++;
                        }

                        // 更新答案
                        ans = Math.max(ans, length);
                    }
                }
            }
        }

        // 输出答案
        console.log(ans);
    });
}

main();

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "strconv"
        "strings"
)

// 定义四个方向的偏移变量
// DIRECTIONS[0]、DIRECTIONS[1]、DIRECTIONS[2]、DIRECTIONS[3]分别表示
// 横向向右、纵向向下、主对角线方向向右下、反对角线反向向左下的4个方向
var DIRECTIONS = [4][2]int{
        {0, 1},  // 横向
        {1, 0},  // 纵向
        {1, 1},  // 主对角线
        {1, -1}, // 反对角线
}

func main() {
        // 读取输入
        scanner := bufio.NewScanner(os.Stdin)
        scanner.Scan()
        dimensions := strings.Split(scanner.Text(), ",")
        n, _ := strconv.Atoi(dimensions[0])
        m, _ := strconv.Atoi(dimensions[1])

        // 初始化二维矩阵
        mat := make([][]string, n)
        for i := 0; i < n; i++ {
                scanner.Scan()
                mat[i] = strings.Split(scanner.Text(), ",")
        }

        // 初始化答案变量，指的是最长连续男生数量
        ans := 0

        // 初始化四个检查矩阵
        check := make([][][]int, 4)
        for k := 0; k < 4; k++ {
                check[k] = make([][]int, n)
                for i := 0; i < n; i++ {
                        check[k][i] = make([]int, m)
                }
        }

        // 从上到下，从左到右顺序枚举矩阵中的每一个元素
        for i := 0; i < n; i++ {
                for j := 0; j < m; j++ {
                        // 考虑横向、纵向、主对角线方向、反对角线方向4个方向
                        for k := 0; k < 4; k++ {
                                // 如果某个M尚未被考虑包含在某段连续的的M中
                                // 则考虑这段M
                                if mat[i][j] == "M" && check[k][i][j] == 0 {
                                        x, y := i, j
                                        dx, dy := DIRECTIONS[k][0], DIRECTIONS[k][1]
                                        length := 0

                                        // 当x和y不越界，且mat[x][y]仍为M时，进行进一步移动的考虑
                                        for x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == "M" {
                                                check[k][x][y] = 1
                                                x += dx
                                                y += dy
                                                length++
                                        }

                                        // 更新答案
                                        if length > ans {
                                                ans = length
                                        }
                                }
                        }
                }
        }

        // 输出答案
        fmt.Println(ans)
}

*代码三：状态压缩写法

Python

# 题目：【模拟】2025A-最大相连男生数
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：模拟，矩阵，位运算，状态压缩
# 代码看不懂的地方，请直接在群上提问


# 四个方向的偏移变量
# DIRECTIONS[0]、DIRECTIONS[1]、DIRECTIONS[2]、DIRECTIONS[3]分别表示
# 横向向右、纵向向下、主对角线方向向右下、反对角线反向向左下的4个方向
DIRECTIONS = [(0, 1), (1, 0), (1, 1), (1, -1)]

# 输入矩阵的行数n，列数m
n, m = map(int, input().split(","))

# 初始化二维矩阵
mat = list()
# 循环n行，输入矩阵
for _ in range(n):
    mat.append(input().split(","))


# 初始化答案变量，指的是最长连续男生数量
ans = 0

# 检查矩阵check，其中的数字的范围为0-15
# 每一个数字的二进制可以由4个数位来表示
# 从低位数起，第0-3位数位
# 分别表示横向、纵向、对角线方向、反对角线方向上
# 某一个M是否已经在某段连续的M中被考虑过
# 譬如3 = bin(0011)，表示对角线和反对角线尚未考虑，横向和纵向已经考虑过了
# 初始化均为0，表示都没有考虑过
check = [[0] * m for _ in range(n)]


# 从上到下，从左到右顺序枚举矩阵中的每一个元素
for i in range(n):
    for j in range(m):
        # 考虑横向、纵向、主对角线方向、反对角线方向4个方向
        for k in range(4):
            # 如果某个M尚未被考虑包含在某段连续的的M中
            # 则考虑这段M
            # (1 >> k)可以得到1左移k位后的结果，
            # 譬如考虑纵向时左移k = 1位得到 2 = bin(0010)
            # 如果check[i][j]和(1 << k)进行与运算后得到0，
            # 说明check[i][j]的二进制表示，从低位数起的第k位为0
            # 第k位对应的方向没有被考虑
            if mat[i][j] == "M" and (check[i][j] & (1 << k)) == 0:
                # (x,y)为移动时的坐标
                # (dx,dy)为横向移动的坐标偏差
                x, y = i, j
                dx, dy = DIRECTIONS[k]
                # 当x和y不越界，且mat[x][y]仍为M时，进行进一步移动的考虑
                # 修改check[k][x][y]为已检查过，且(x,y)修改
                while 0 <= x < n and 0 <= y < m and mat[x][y] == "M":
                    # 将check[x][y]的二进制表示的第k位，通过或运算从0修改为1
                    check[x][y] |= (1 << k)
                    x += dx
                    y += dy
                # 退出while循环后，此段横向的连续的M的长度为x-i或y-j（取其中较大值），更新答案
                ans = max(ans, max(x-i, y-j))

print(ans)

Java

import java.util.Scanner;

public class Main {

    // 四个方向的偏移变量
    // DIRECTIONS[0]、DIRECTIONS[1]、DIRECTIONS[2]、DIRECTIONS[3]分别表示
    // 横向向右、纵向向下、主对角线方向向右下、反对角线方向向左下的4个方向
    private static final int[][] DIRECTIONS = {
            {0, 1},   // 横向向右
            {1, 0},   // 纵向向下
            {1, 1},   // 主对角线方向向右下
            {1, -1}   // 反对角线方向向左下
    };

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入矩阵的行数n，列数m
        String[] input = scanner.nextLine().split(",");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        // 初始化二维矩阵
        String[][] mat = new String[n][m];
        // 循环n行，输入矩阵
        for (int i = 0; i < n; i++) {
            mat[i] = scanner.nextLine().split(",");
        }

        // 初始化答案变量，指的是最长连续男生数量
        int ans = 0;

        // 检查矩阵check，其中的数字的范围为0-15
        // 每一个数字的二进制可以由4个数位来表示
        // 从低位数起，第0-3位数位
        // 分别表示横向、纵向、对角线方向、反对角线方向上
        // 某一个M是否已经在某段连续的M中被考虑过
        // 初始化均为0，表示都没有考虑过
        int[][] check = new int[n][m];

        // 从上到下，从左到右顺序枚举矩阵中的每一个元素
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 考虑横向、纵向、主对角线方向、反对角线方向4个方向
                for (int k = 0; k < 4; k++) {
                    // 如果某个M尚未被考虑包含在某段连续的的M中
                    // 则考虑这段M
                    // (1 >> k)可以得到1左移k位后的结果，
                    // 譬如考虑纵向时左移k = 1位得到 2 = bin(0010)
                    // 如果check[i][j]和(1 << k)进行与运算后得到0，
                    // 说明check[i][j]的二进制表示，从低位数起的第k位为0
                    // 第k位对应的方向没有被考虑
                    if (mat[i][j].equals("M") && (check[i][j] & (1 << k)) == 0) {
                        // (x,y)为移动时的坐标
                        // (dx,dy)为移动的坐标偏差
                        int x = i, y = j;
                        int dx = DIRECTIONS[k][0], dy = DIRECTIONS[k][1];
                        // 当x和y不越界，且mat[x][y]仍为M时，进行进一步移动的考虑
                        // 修改check[x][y]为已检查过，且(x,y)修改
                        while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y].equals("M")) {
                            // 将check[x][y]的二进制表示的第k位，通过或运算从0修改为1
                            check[x][y] |= (1 << k);
                            x += dx;
                            y += dy;
                        }
                        // 退出while循环后，此段方向的连续的M的长度为x-i或y-j（取其中较大值），更新答案
                        ans = Math.max(ans, Math.max(x - i, y - j));
                    }
                }
            }
        }

        // 输出答案
        System.out.println(ans);

        scanner.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 四个方向的偏移变量
// DIRECTIONS[0]、DIRECTIONS[1]、DIRECTIONS[2]、DIRECTIONS[3]分别表示
// 横向向右、纵向向下、主对角线方向向右下、反对角线方向向左下的4个方向
const int DIRECTIONS[4][2] = {
    {0, 1},   // 横向向右
    {1, 0},   // 纵向向下
    {1, 1},   // 主对角线方向向右下
    {1, -1}   // 反对角线方向向左下
};

int main() {
    // 输入矩阵的行数n，列数m
    int n, m;
    char comma;
    cin >> n >> comma >> m;
    cin.ignore(); // 忽略换行符

    // 初始化二维矩阵
    vector<vector<string>> mat(n, vector<string>(m));
    // 循环n行，输入矩阵
    for (int i = 0; i < n; i++) {
        string line;
        getline(cin, line);
        size_t pos = 0;
        for (int j = 0; j < m; j++) {
            size_t next_pos = line.find(',', pos);
            mat[i][j] = line.substr(pos, next_pos - pos);
            pos = next_pos + 1;
        }
    }

    // 初始化答案变量，指的是最长连续男生数量
    int ans = 0;

    // 检查矩阵check，其中的数字的范围为0-15
    // 每一个数字的二进制可以由4个数位来表示
    // 从低位数起，第0-3位数位
    // 分别表示横向、纵向、对角线方向、反对角线方向上
    // 某一个M是否已经在某段连续的M中被考虑过
    // 初始化均为0，表示都没有考虑过
    vector<vector<int>> check(n, vector<int>(m, 0));

    // 从上到下，从左到右顺序枚举矩阵中的每一个元素
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 考虑横向、纵向、主对角线方向、反对角线方向4个方向
            for (int k = 0; k < 4; k++) {
                // 如果某个M尚未被考虑包含在某段连续的的M中
                // 则考虑这段M
                if (mat[i][j] == "M" && (check[i][j] & (1 << k)) == 0) {
                    // (x,y)为移动时的坐标
                    // (dx,dy)为移动的坐标偏差
                    int x = i, y = j;
                    int dx = DIRECTIONS[k][0], dy = DIRECTIONS[k][1];
                    // 当x和y不越界，且mat[x][y]仍为M时，进行进一步移动的考虑
                    // 修改check[x][y]为已检查过，且(x,y)修改
                    while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == "M") {
                        // 将check[x][y]的二进制表示的第k位，通过或运算从0修改为1
                        check[x][y] |= (1 << k);
                        x += dx;
                        y += dy;
                    }
                    // 退出while循环后，此段方向的连续的M的长度为x-i或y-j（取其中较大值），更新答案
                    ans = max(ans, max(x - i, y - j));
                }
            }
        }
    }

    // 输出答案
    cout << ans << endl;

    return 0;
}

C

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

// 定义四个方向的偏移变量
// DIRECTIONS[0]、DIRECTIONS[1]、DIRECTIONS[2]、DIRECTIONS[3]分别表示
// 横向向右、纵向向下、主对角线方向向右下、反对角线反向向左下的4个方向
const int DIRECTIONS[4][2] = {
    {0, 1},  // 横向
    {1, 0},  // 纵向
    {1, 1},  // 主对角线
    {1, -1}  // 反对角线
};

int main() {
    int n, m;
    // 输入矩阵的行数n，列数m
    scanf("%d,%d", &n, &m);

    // 初始化二维矩阵
    char mat[n][m + 1];  // +1是为了处理输入时的逗号分隔
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf(" %c,", &mat[i][j]);  // 每个元素以逗号分隔输入
        }
    }

    // 初始化答案变量，指的是最长连续男生数量
    int ans = 0;

    // 检查矩阵check，其中的数字范围为0-15
    // 使用4个位来表示横向、纵向、对角线方向、反对角线方向是否已经考虑
    int check[n][m];
    memset(check, 0, sizeof(check));

    // 从上到下，从左到右顺序枚举矩阵中的每一个元素
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 考虑横向、纵向、主对角线方向、反对角线方向4个方向
            for (int k = 0; k < 4; k++) {
                // 如果某个M尚未被考虑包含在某段连续的的M中
                // 则考虑这段M
                if (mat[i][j] == 'M' && (check[i][j] & (1 << k)) == 0) {
                    int x = i, y = j;
                    int dx = DIRECTIONS[k][0], dy = DIRECTIONS[k][1];
                    int length = 0;

                    // 当x和y不越界，且mat[x][y]仍为M时，进行进一步移动的考虑
                    while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == 'M') {
                        // 将check[x][y]的二进制表示的第k位，通过或运算从0修改为1
                        check[x][y] |= (1 << k);
                        x += dx;
                        y += dy;
                        length++;
                    }
                    // 更新答案
                    if (length > ans) {
                        ans = length;
                    }
                }
            }
        }
    }

    // 输出答案
    printf("%d\n", ans);

    return 0;
}

Node JavaScript

const readline = require("readline");

// 定义四个方向的偏移变量
// DIRECTIONS[0]、DIRECTIONS[1]、DIRECTIONS[2]、DIRECTIONS[3]分别表示
// 横向向右、纵向向下、主对角线方向向右下、反对角线反向向左下的4个方向
const DIRECTIONS = [
    [0, 1],  // 横向
    [1, 0],  // 纵向
    [1, 1],  // 主对角线
    [1, -1], // 反对角线
];

function main() {
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout,
    });

    let inputLines = [];
    rl.on("line", (line) => {
        inputLines.push(line);
    });

    rl.on("close", () => {
        // 读取矩阵的行数和列数
        const [n, m] = inputLines[0].split(",").map(Number);

        // 初始化二维矩阵
        const mat = [];
        for (let i = 1; i <= n; i++) {
            mat.push(inputLines[i].split(","));
        }

        // 初始化答案变量，指的是最长连续男生数量
        let ans = 0;

        // 检查矩阵check，其中的数字范围为0-15
        // 使用4个位来表示横向、纵向、对角线方向、反对角线方向是否已经考虑
        const check = Array.from({ length: n }, () => Array(m).fill(0));

        // 从上到下，从左到右顺序枚举矩阵中的每一个元素
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < m; j++) {
                // 考虑横向、纵向、主对角线方向、反对角线方向4个方向
                for (let k = 0; k < 4; k++) {
                    // 如果某个M尚未被考虑包含在某段连续的的M中
                    // 则考虑这段M
                    if (mat[i][j] === "M" && (check[i][j] & (1 << k)) === 0) {
                        let x = i, y = j;
                        const [dx, dy] = DIRECTIONS[k];
                        let length = 0;

                        // 当x和y不越界，且mat[x][y]仍为M时，进行进一步移动的考虑
                        while (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] === "M") {
                            // 将check[x][y]的二进制表示的第k位，通过或运算从0修改为1
                            check[x][y] |= (1 << k);
                            x += dx;
                            y += dy;
                            length++;
                        }
                        // 更新答案
                        ans = Math.max(ans, length);
                    }
                }
            }
        }

        // 输出答案
        console.log(ans);
    });
}

main();

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "strconv"
        "strings"
)

// 定义四个方向的偏移变量
// DIRECTIONS[0]、DIRECTIONS[1]、DIRECTIONS[2]、DIRECTIONS[3]分别表示
// 横向向右、纵向向下、主对角线方向向右下、反对角线反向向左下的4个方向
var DIRECTIONS = [4][2]int{
        {0, 1},  // 横向
        {1, 0},  // 纵向
        {1, 1},  // 主对角线
        {1, -1}, // 反对角线
}

func main() {
        // 读取输入
        scanner := bufio.NewScanner(os.Stdin)
        scanner.Scan()
        dimensions := strings.Split(scanner.Text(), ",")
        n, _ := strconv.Atoi(dimensions[0])
        m, _ := strconv.Atoi(dimensions[1])

        // 初始化二维矩阵
        mat := make([][]string, n)
        for i := 0; i < n; i++ {
                scanner.Scan()
                mat[i] = strings.Split(scanner.Text(), ",")
        }

        // 初始化答案变量，指的是最长连续男生数量
        ans := 0

        // 检查矩阵check，其中的数字范围为0-15
        // 使用4个位来表示横向、纵向、对角线方向、反对角线方向是否已经考虑
        check := make([][]int, n)
        for i := 0; i < n; i++ {
                check[i] = make([]int, m)
        }

        // 从上到下，从左到右顺序枚举矩阵中的每一个元素
        for i := 0; i < n; i++ {
                for j := 0; j < m; j++ {
                        // 考虑横向、纵向、主对角线方向、反对角线方向4个方向
                        for k := 0; k < 4; k++ {
                                // 如果某个M尚未被考虑包含在某段连续的的M中
                                // 则考虑这段M
                                if mat[i][j] == "M" && (check[i][j]&(1<<k)) == 0 {
                                        x, y := i, j
                                        dx, dy := DIRECTIONS[k][0], DIRECTIONS[k][1]
                                        length := 0

                                        // 当x和y不越界，且mat[x][y]仍为M时，进行进一步移动的考虑
                                        for x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == "M" {
                                                // 将check[x][y]的二进制表示的第k位，通过或运算从0修改为1
                                                check[x][y] |= (1 << k)
                                                x += dx
                                                y += dy
                                                length++
                                        }
                                        // 更新答案
                                        if length > ans {
                                                ans = length
                                        }
                                }
                        }
                }
        }

        // 输出答案
        fmt.Println(ans)
}

时空复杂度

时间复杂度：O(4NM)。

空间复杂度：O(4NM)。检查数组所占空间。如果使用状态压缩，则降低到O(NM)。