华为OD机试真题——洞穴探险（2025A卷：200分）Java/python/JavaScript/C/C++/GO最佳实现
2025 A卷 200分 题型
本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；
并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；
本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》
华为OD机试真题《洞穴探险》：
文章快捷目录
题目描述及说明
Java
python
JavaScript
C
GO
题目名称：洞穴探险
- 知识点：字符串处理、正则匹配（或栈操作）、逻辑判断
- 时间限制：1秒
- 空间限制：256MB
- 限定语言：不限
题目描述
某探险队负责对地下洞穴进行探险。探险队成员在进行探险任务时，随身携带的记录器会不定期地记录自身的坐标，但在记录的间隙中也会记录其他数据。探索工作结束后，探险队需要获取到某成员在探险过程中相对于探险队总部的最远足迹位置。
坐标规则
- 坐标格式为
(x,y)，例如(1,2)、(100,200)，其中0 < x < 1000，0 < y < 1000。 - 非法坐标包括以下情况：
- 数字前导零（如
(01,1)、(1,01)）； - 坐标值为0或超出范围（如
(0,100)）。
- 数字前导零（如
距离计算
- 总部坐标为
(0,0)，某位置(x,y)的相对距离为 ( x^2 + y^2 )。 - 若两个坐标距离相同，则以第一次出现的坐标为准。
- 若所有坐标均非法，输出
(0,0)。
输入描述
一行字符串，表示记录仪中的数据（可能包含非坐标字符）。例如：
ferga13fdsf3(100,200)f2r3rfasf(300,400)
输出描述
最远足迹坐标，如：
(300,400)
示例
- 输入：
ferg(3,10)a13fdsf3(3,4)f2r3rfasf(5,10)
输出：(5,10)（合法坐标中距离最大） - 输入：
asfefaweawfaw(0,1)fe
输出：(0,0)（坐标非法）
备注
无需处理嵌套括号（如 sfsdfsd((1,2))）。
Java
问题分析
题目要求从输入字符串中提取所有合法的坐标，并找到距离总部（0,0）最远的坐标。若所有坐标均非法，则返回(0,0)。合法坐标需满足以下条件：
- 格式为(x,y)，其中x和y为数字且无前导零（除非数字本身为0，但x和y必须大于0且小于1000）。
- 0 < x < 1000，0 < y < 1000。
解题思路
- 正则匹配：使用正则表达式提取所有可能的坐标。
- 合法性验证：
- 检查x和y是否有前导零。
- 检查x和y的数值范围是否合法。
- 计算距离：对合法坐标计算其到总部(0,0)的欧氏距离平方（x² + y²），记录最大距离对应的坐标。
- 处理边界：若无合法坐标，返回(0,0)。
代码实现
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String input = scanner.nextLine();scanner.close();Pattern pattern = Pattern.compile("\\((\\d+),(\\d+)\\)"); // 匹配(x,y)格式Matcher matcher = pattern.matcher(input);int maxDistance = -1;String maxCoordinate = null;while (matcher.find()) {String xStr = matcher.group(1); // 提取x部分字符串String yStr = matcher.group(2); // 提取y部分字符串// 检查前导零：若长度>1，则首字符不能为0boolean xValid = (xStr.length() == 1) || (xStr.length() > 1 && xStr.charAt(0) != '0');boolean yValid = (yStr.length() == 1) || (yStr.length() > 1 && yStr.charAt(0) != '0');if (!xValid || !yValid) {continue;}// 转换为整数并验证范围int x = Integer.parseInt(xStr);int y = Integer.parseInt(yStr);if (x <= 0 || x >= 1000 || y <= 0 || y >= 1000) {continue; // 数值非法}// 计算距离int distance = x * x + y * y;if (distance > maxDistance) {maxDistance = distance;maxCoordinate = "(" + x + "," + y + ")"; // 更新最大坐标}}System.out.println(maxCoordinate != null ? maxCoordinate : "(0,0)");}
}
代码解析
- 正则匹配：
Pattern.compile("\\((\\d+),(\\d+)\\)")匹配形如(x,y)的字符串，其中\\d+表示一个或多个数字。 - 提取坐标：
matcher.find()循环遍历所有匹配的坐标，group(1)和group(2)分别提取x和y的字符串形式。 - 前导零检查：若x或y的字符串长度大于1且首字符为0，视为非法。
- 数值范围检查：将x和y转换为整数后，检查是否满足0 < x < 1000和0 < y < 1000。
- 距离计算：对合法坐标计算x² + y²，并更新最大距离及对应坐标。
- 结果输出：若无合法坐标，输出(0,0)，否则输出最大距离对应的坐标。
示例测试
-
输入：
ferg(3,10)a13fdsf3(3,4)f2r3rfasf(5,10)
输出：(5,10)
解释：合法坐标有(3,10)、(3,4)、(5,10)，最大距离为5² + 10² = 125。 -
输入：
asfefaweawfaw(0,1)fe
输出：(0,0)
解释：坐标(0,1)中x=0非法，无合法坐标。 -
输入：
(01,2)(100,02)(100,999)
输出：(100,999)
解释：前两个坐标因前导零或数值非法被过滤，第三个坐标合法且距离最大。
综合分析
- 时间复杂度：O(n)，其中n为输入字符串长度。正则匹配和遍历均为线性复杂度。
- 空间复杂度：O(1)，仅需存储临时变量。
- 优势：
- 高效性：正则表达式快速定位坐标，避免逐字符遍历。
- 鲁棒性：严格校验前导零和数值范围，确保合法坐标正确性。
- 适用性：完美处理题目约束条件，适用于大范围输入数据。
python
问题分析
题目要求从输入字符串中提取所有合法的坐标，并找到距离总部（0,0）最远的坐标。若所有坐标均非法，则返回(0,0)。合法坐标需满足以下条件：
- 格式为(x,y)，其中x和y为数字且无前导零（除非数字本身为0，但x和y必须大于0且小于1000）。
- 0 < x < 1000，0 < y < 1000。
解题思路
- 正则匹配：使用正则表达式提取所有可能的坐标。
- 合法性验证：
- 检查x和y是否有前导零。
- 检查x和y的数值范围是否合法。
- 计算距离：对合法坐标计算其到总部(0,0)的欧氏距离平方（x² + y²），记录最大距离对应的坐标。
- 处理边界：若无合法坐标，返回(0,0)。
代码实现
import redef find_farthest_coordinate(input_str):max_distance = -1max_coord = Nonepattern = re.compile(r'\((\d+),(\d+)\)') # 正则匹配坐标格式for match