学校组织活动，将学生排成一个矩形方阵。
请在矩形方阵中找到最大的位置相连的男生数量。
这个相连位置在一个直线上，方向可以是水平的，垂直的，成对角线的或者呈反对角线的。
注：学生个数不会超过10000
3,4
F,M,M,F
F,M,M,F
F,F,F,M
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">3
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">主要步骤：
输入解析：
输入的数据格式为：第一行包含网格的行数和列数，后续的每一行表示网格的一行，元素用逗号分隔。我们需要将这些输入转换为二维数组 grid，并且将行数和列数分别存储为 rows 和 cols。
遍历网格：
对每一个 “M”（男孩）字符，我们需要在四个方向上进行延伸，尝试找出以该点为起始点的最大连通序列。
四个方向的偏移量是：右（(0, 1)）、下（(1, 0)）、右下（(1, 1)）和左下（(1, -1)）。这四个方向涵盖了水平、垂直和两条对角线。
计数最大连通序列：
对于每个 “M” 位置，从它开始沿四个方向进行扩展，计算出连通的 “M” 数量，更新最大长度。
返回最大连通长度：
记录遍历过程中发现的最大连通长度并返回。
import sys
def main():
# 读取输入数据，第一行包含行列数，后续行表示网格数据
input = sys.stdin.read().splitlines()
rows, cols = map(int, input[0].split(",")) # 获取行数和列数
# 生成网格，网格是一个二维列表，元素是 "M" 或其他字符
grid = [input[i + 1].split(",") for i in range(rows)]
# 找到最大连通 "M" 的函数
def find_max_connected_boys():
max_length = 0 # 初始化最大长度为 0
# 定义四个方向：右、下、右下、左下
directions = [(0, 1), (1, 0), (1, 1), (1, -1)]
# 遍历整个网格
for r in range(rows):
for c in range(cols):
# 如果当前位置是 "M"（男孩），就开始从该点扩展
if grid[r][c] == "M":
# 对于每个方向，计算连通 "M" 的最大长度
for dr, dc in directions:
max_length = max(max_length, count_length(r, c, dr, dc))
return max_length # 返回最大连通 "M" 的长度
# 计算从 (r, c) 开始，沿方向 (dr, dc) 扩展的 "M" 连通长度
def count_length(r, c, dr, dc):
length = 0
# 在当前方向上继续检查，直到超出网格或者不再是 "M"
while 0 <= r < rows and 0 <= c < cols and grid[r][c] == "M":
length += 1 # 发现一个 "M" 字符，增加长度
r += dr # 根据方向移动到下一个位置
c += dc
return length # 返回该方向上连通 "M" 的长度
# 打印最大连通 "M" 的长度
print(find_max_connected_boys())
# 程序入口
if __name__ == "__main__":
main()
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">主要步骤：
输入解析：
输入数据首先提供了网格的行数和列数，然后是网格本身的内容。我们需要将这些输入转换为一个二维数组 grid，并且将行数和列数分别存储为 rows 和 cols。
遍历网格：
对每一个 “M”（男孩）字符，我们需要在四个方向上进行扩展，尝试找出以该点为起始点的最大连通序列。
四个方向的偏移量是：右（(0, 1)）、下（(1, 0)）、右下（(1, 1)）和左下（(1, -1)）。这四个方向涵盖了水平、垂直和两条对角线。
计数最大连通序列：
对于每个 “M” 位置，从它开始沿四个方向进行扩展，计算出连通的 “M” 数量，更新最大长度。
返回最大连通长度：
记录遍历过程中发现的最大连通长度并返回。
import java.util.Scanner;
public class Main {
// 行数和列数
static int rows, cols;
// 网格数组
static String[][] grid;
public static void main(String[] args) {
// 创建扫描器，设置分隔符为逗号和换行符
Scanner scanner = new Scanner(System.in).useDelimiter("[,\n]");
// 读取行数和列数
rows = scanner.nextInt();
cols = scanner.nextInt();
// 初始化网格
grid = new String[rows][cols];
// 填充网格数据
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
grid[i][j] = scanner.next();
}
}
// 输出最大连通 "M" 的长度
System.out.println(findMaxConnectedBoys());
}
// 找到最大连通 "M" 的长度
private static int findMaxConnectedBoys() {
int maxLength = 0; // 初始化最大长度为 0
// 四个方向的偏移量，分别是右、下、右下、左下
int[][] directions = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};
// 遍历每一个网格中的元素
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
// 如果当前位置是 "M"（男孩）
if ("M".equals(grid[r][c])) {
// 对每一个方向进行检查
for (int[] direction : directions) {
// 计算当前方向上的连通长度
int currentLength = countLength(r, c, direction);
// 更新最大长度
maxLength = Math.max(maxLength, currentLength);
}
}
}
}
// 返回最大长度
return maxLength;
}
// 计算从 (r, c) 开始，在给定方向上延伸的 "M" 连通长度
private static int countLength(int r, int c, int[] direction) {
int length = 0;
// 检查当前方向上是否仍然是 "M"，并且不越界
while (r >= 0 && r < rows && c >= 0 && c < cols && "M".equals(grid[r][c])) {
length++; // 每找到一个 "M" 就增加长度
r += direction[0]; // 根据方向更新行号
c += direction[1]; // 根据方向更新列号
}
return length; // 返回连通的长度
}
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">更新中
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">更新中
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">解题思路
题目要求在一个 n x m 的矩阵中，寻找连续的 “M”（表示男孩）字符的最长连通序列。我们可以沿着四个方向（水平、垂直、对角线）进行搜索，每次从矩阵中的一个 “M” 字符开始，沿着某个方向扩展，直到遇到非 “M” 字符或者越界。
具体的解题步骤如下：
输入解析：
第一行输入提供了矩阵的行数 n 和列数 m。
随后的每一行表示矩阵的一行，矩阵元素之间以逗号分隔。我们需要将这些输入数据解析为一个二维矩阵。
深度优先搜索（DFS）：
对每一个 “M” 字符，尝试沿着四个方向（右、下、右下、左下）进行扩展。每扩展一次，计数器增加，并继续沿该方向扩展，直到遇到边界或者非 “M” 字符。
每个 “M” 字符都可能是一个连通序列的起点，因此需要尝试从每个 “M” 开始沿四个方向进行搜索，计算当前方向上的连通长度。
更新最大长度：
在遍历过程中，始终记录下遇到的最大连通长度，并返回最终结果。
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
// 四个可能的方向：右、下、右下、左下
const directions = [
[0, 1], // 右
[1, 0], // 下
[1, 1], // 右下对角线
[1, -1] // 左下对角线
];
// 用于存储输入的行数据
const lines = [];
let n, m;
// 读取输入的每一行
rl.on("line", (line) => {
lines.push(line);
// 第一个输入是矩阵的行数和列数，解析并赋值给 n 和 m
if (lines.length === 1) {
[n, m] = lines[0].split(",").map(Number);
}
// 当读取到所有矩阵数据后，开始处理
if (n && lines.length === n + 1) {
// 处理输入的矩阵数据，去除首行，剩下的都是矩阵内容
lines.shift();
const matrix = lines.map((line) => line.split(","));
// 输出最大连通 "M" 序列的长度
console.log(findMaxSequence(matrix, n, m));
// 清空输入行数据，准备下一轮输入
lines.length = 0;
});
// 计算矩阵中最大连通 "M" 序列的函数
function findMaxSequence(matrix, n, m) {
let maxLength = 0;
// 深度优先搜索：从当前位置开始，沿着给定方向扩展，返回扩展的 "M" 序列长度
function dfs(x, y, dx, dy) {
let length = 1; // 当前 "M" 本身已经算作一个序列
let newX = x + dx; // 下一行坐标
let newY = y + dy; // 下一列坐标
// 持续沿方向扩展，直到越界或遇到非 "M" 字符
while (newX >= 0 && newX < n && newY >= 0 && newY < m && matrix[newX][newY] === "M") {
length++; // 继续增加序列长度
newX += dx; // 更新行坐标
newY += dy; // 更新列坐标
}
return length; // 返回该方向上的连通长度
}
// 遍历矩阵中的每一个点
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
// 如果当前位置是 "M"（表示男孩）
if (matrix[i][j] === "M") {
// 对每一个方向进行深度优先搜索
for (let [dx, dy] of directions) {
// 更新最大连通长度
maxLength = Math.max(maxLength, dfs(i, j, dx, dy));
}
}
}
}
return maxLength; // 返回最大连通 "M" 的长度
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：