学生方阵 --- 华为od刷题记录

题目描述

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

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

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

注：学生个数不会超过10000

输入描述

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

输出描述

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

用例

参考文章

【华为OD机试 】 学生方阵（C++ Java JavaScript Python 4种语言）

C++

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
void getMaxConnected(vector<vector<string>>& students, int row, int column, vector<int>& res) {
    int len = 1; // 初始化连续的M的个数为1
    int a = 0, b = 0; // 初始化行和列的索引
    int m = students.size(), n = students[0].size(); // 获取方阵的行数和列数
    if (column < n) {  // 从左往右搜索
        a = row;
        b = column;
        while (b < n - 1 && students[a][++b] == "M") { // 不越界且下一个元素为M
            len++; // 连续的M的个数加1
        }
        res.push_back(len); // 把连续的M的个数加入结果数组
        len = 1; // 重新初始化连续的M的个数为1
    }
    if (row < m) {  // 从上往下搜索
        a = row;
        b = column;
        while (a < m - 1 && students[++a][b] == "M") { // 不越界且下一个元素为M
            len++; // 连续的M的个数加1
        }
        res.push_back(len); // 把连续的M的个数加入结果数组
        len = 1; // 重新初始化连续的M的个数为1
    }
    if (row < m && column < n) {  // 对角线搜索
        a = row;
        b = column;
        while ((a < m - 1 && b < n - 1) && students[++a][++b] == "M") { // 不越界且下一个元素为M
            len++; // 连续的M的个数加1
        }
        res.push_back(len); // 把连续的M的个数加入结果数组
        len = 1; // 重新初始化连续的M的个数为1
    }
    if (row >= 0 && column < n) {  // 从右往左搜索
        a = row;
        b = column;
        while ((a > 0 && b < n - 1) && students[--a][++b] == "M") { // 不越界且下一个元素为M
            len++; // 连续的M的个数加1
        }
        res.push_back(len); // 把连续的M的个数加入结果数组
    }
}
 
int main() {
    //输入
    string input_str;
    // 字符串输入
    getline(cin,input_str);
    
    int row = stoi(input_str.substr(0, input_str.find(",")));
    int column = stoi(input_str.substr(input_str.find(",")+1));
    //cout << row << " " << column<<endl; 
    // 初始化方阵
    vector<vector<string>> students;
    for (int i=0;i<row;i++) {
        string student_str;
        getline(cin,student_str);
        vector<string> temp;
        
        while (student_str.find(",") != string::npos) { // 当字符串中还有逗号
            int found = student_str.find(",");
            temp.push_back(student_str.substr(0, found)); // 把逗号前面的字符串加入临时数组
            student_str = student_str.substr(found + 1); // 更新字符串，去掉逗号和前面的字符串
        } 
        temp.push_back(student_str); // 把最后一个字符串加入临时数组
        students.push_back(temp); // 把临时数组加入方阵
    }
    
    vector<int> max_res; // 初始化结果数组
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < column; j++) {
            //遇到M则开始找
            if (students[i][j] == "M") { // 如果当前元素为M
                getMaxConnected(students, i, j, max_res); // 在四个方向上搜索连续的M
            }
        }
    }
    sort(max_res.begin(), max_res.end()); // 对结果数组排序
    cout << max_res[max_res.size()-1]; // 输出最大的连续的M的个数
    
    return 0;
}