#P3250. 学生方阵(200分)
-
1000ms
Tried: 121
Accepted: 23
Difficulty: 3
所属公司 :
华为od
学生方阵(200分)
题面描述
学校组织活动,将学生排成一个矩形方阵。请在矩形方阵中找到最大的位置相连的男生数量。这个相连的位置可以在一个直线上,方向可以是水平的、垂直的、主对角线的或者反对角线的。
注:学生总数不会超过10,000人。
思路
为了找到矩形方阵中最长的连续相连的男生数量,我们需要遍历矩阵中的每一个位置,对于每一个男生的位置,向四个可能的方向(水平、垂直、主对角线、反对角线)延伸,计算连续的男生数量,并记录其中的最大值。
具体步骤如下:
-
输入处理:
- 读取矩阵的行数和列数。
- 读取接下来的n行,构建矩阵。
-
遍历矩阵:
- 对于矩阵中的每一个位置,如果该位置是男生(
'M'),则:- 向四个方向延伸,计算连续的男生数量:
- 水平向右:检查当前位置右侧的连续男生。
- 垂直向下:检查当前位置下方的连续男生。
- 主对角线:检查当前位置右下方的连续男生。
- 反对角线:检查当前位置左下方的连续男生。
- 更新最大连续男生数量。
- 向四个方向延伸,计算连续的男生数量:
- 对于矩阵中的每一个位置,如果该位置是男生(
-
输出结果:
- 输出记录的最大连续男生数量。
由于矩阵的大小不会超过100x100,遍历每一个位置并检查四个方向的复杂度是可以接受的。
cpp
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;
// 分割字符串的函数,支持多种分隔符
vector<string> split(const string &s, const string &delimiters) {
vector<string> tokens;
size_t prev = 0, pos;
while ((pos = s.find_first_of(delimiters, prev)) != string::npos) {
if (pos > prev)
tokens.emplace_back(s.substr(prev, pos - prev));
prev = pos + 1;
}
if (prev < s.length())
tokens.emplace_back(s.substr(prev, string::npos));
return tokens;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
string line;
// 读取第一行,获取n和m
if(!getline(cin, line)){
// 输入为空
return 0;
}
// 尝试以逗号分隔
vector<string> dims = split(line, ", ");
if(dims.size() < 2){
// 如果以逗号分隔失败,尝试以空格分隔
dims = split(line, " ");
}
if(dims.size() < 2){
// 输入格式错误
cerr << "输入格式错误:第一行应包含行数和列数,以逗号或空格分隔。\n";
return 0;
}
n = stoi(dims[0]);
m = stoi(dims[1]);
// 读取接下来的n行,构建矩阵
vector<vector<char>> matrix(n, vector<char>(m, 'F'));
for(int i=0;i<n;i++){
if(!getline(cin, line)){
// 如果行数不足
cerr << "输入行数不足,预期:" << n << ",实际:" << i << "\n";
return 0;
}
vector<string> elements = split(line, ",");
for(int j=0; j<m && j < (int)elements.size(); j++){
if(elements[j].empty()){
matrix[i][j] = 'F'; // 默认女生
}
else{
// 去除可能的空格
size_t start = elements[j].find_first_not_of(" ");
if(start != string::npos){
matrix[i][j] = elements[j][start];
}
else{
matrix[i][j] = 'F';
}
}
}
}
// 定义四个方向:水平,垂直,主对角线,反对角线
vector<pair<int, int>> directions = {
{0,1}, // 水平向右
{1,0}, // 垂直向下
{1,1}, // 主对角线
{1,-1} // 反对角线
};
int max_count = 0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(matrix[i][j] == 'M'){
for(auto dir : directions){
int count = 1;
int x = i + dir.first;
int y = j + dir.second;
while(x >=0 && x < n && y >=0 && y < m && matrix[x][y] == 'M'){
count++;
x += dir.first;
y += dir.second;
}
if(count > max_count)
max_count = count;
}
}
}
}
cout << max_count;
return 0;
}
python
def split_string(s, delimiters):
"""根据多个分隔符分割字符串,返回分割后的字符串列表"""
tokens = []
prev = 0
for delimiter in delimiters:
parts = s.split(delimiter)
for part in parts:
if part:
tokens.append(part.strip()) # 去除前后空格
prev += len(parts) - 1 # 更新prev
return tokens
def main():
import sys
# 读取第一行,获取n和m
line = sys.stdin.readline().strip()
# 尝试以空格分隔行数和列数
dims = split_string(line, [" "])
if len(dims) < 2:
print("输入格式错误:第一行应包含行数和列数,以空格分隔。")
return
n = int(dims[0])
m = int(dims[1])
# 读取接下来的n行,构建矩阵
matrix = []
for _ in range(n):
line = sys.stdin.readline().strip()
elements = split_string(line, [','])
matrix.append([elements[j].strip() if j < len(elements) and elements[j].strip() else 'F' for j in range(m)])
# 定义四个方向:水平,垂直,主对角线,反对角线
directions = [
(0, 1), # 水平向右
(1, 0), # 垂直向下
(1, 1), # 主对角线
(1, -1) # 反对角线
]
max_count = 0
for i in range(n):
for j in range(m):
if matrix[i][j] == 'M':
for dx, dy in directions:
count = 1
x, y = i + dx, j + dy
while 0 <= x < n and 0 <= y < m and matrix[x][y] == 'M':
count += 1
x += dx
y += dy
max_count = max(max_count, count)
print(max_count)
if __name__ == "__main__":
main()
java
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static List<String> splitString(String s, String[] delimiters) {
List<String> tokens = new ArrayList<>();
String[] parts = s.split("[ ]+"); // 使用空格分割
for (String part : parts) {
if (!part.isEmpty()) {
tokens.add(part.trim());
}
}
return tokens;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取第一行,获取n和m
String line = scanner.nextLine().trim();
List<String> dims = splitString(line, new String[]{" "});
if (dims.size() < 2) {
System.out.println("输入格式错误:第一行应包含行数和列数,以空格分隔。");
return;
}
int n = Integer.parseInt(dims.get(0));
int m = Integer.parseInt(dims.get(1));
// 读取接下来的n行,构建矩阵
char[][] matrix = new char[n][m];
for (int i = 0; i < n; i++) {
line = scanner.nextLine().trim();
String[] elements = line.split(",");
for (int j = 0; j < m; j++) {
if (j < elements.length && !elements[j].trim().isEmpty()) {
matrix[i][j] = elements[j].trim().charAt(0);
} else {
matrix[i][j] = 'F'; // 默认女生
}
}
}
// 定义四个方向:水平,垂直,主对角线,反对角线
int[][] directions = {
{0, 1}, // 水平向右
{1, 0}, // 垂直向下
{1, 1}, // 主对角线
{1, -1} // 反对角线
};
int maxCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 'M') {
for (int[] dir : directions) {
int count = 1;
int x = i + dir[0];
int y = j + dir[1];
while (x >= 0 && x < n && y >= 0 && y < m && matrix[x][y] == 'M') {
count++;
x += dir[0];
y += dir[1];
}
maxCount = Math.max(maxCount, count);
}
}
}
}
System.out.println(maxCount);
scanner.close();
}
}
题目内容
学校组织活动,将学生排成一个矩形方阵。
请在矩形方阵中找到最大的位置相连的男生数量。
这个相连位置在一个直线上,方向可以是水平的,垂直的,成对角线的或者呈反对角线的。
注:学生个数不会超过10000
输入描述
输入的第一行为矩阵的行数和列数,接下来的n行为矩阵元素,元素间用”,”分隔。
输出描述
输出一个整数,表示矩阵中最长的位置相连的男生个数。
样例1
输入
3,4
F,M,M,F
F,M,M,F
F,F,F,M
输出
3
说明
