2026 华为OD机试真题 4月8日华为OD上机新系统考试真题 200 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

小王在玩一款叫做直捣黄龙的小游戏，在该游戏中他需要从入口位置进入敌营，绕过哨兵的层层封锁，达到敌军司令部实施斩首行动。

敌军阵营是一个 $n*n$ 的矩阵，入口在坐标 $(0,n/2)$，敌军司令部在坐标 $(n-1,n/2)$，每个哨兵警戒以自己为中心的9宫格，一旦被哨兵发现则行动失败。

同时穿越敌营耗时越长，被发现的概率越高，因此小王需要寻找到可以绕过警戒到达敌军司令部的最短路径。

请你设计一个小程序，帮助小王统计这样的路径有多少条，以及路径长度。

规则说明:

1.其中 $n$ 为大于 $1$ 的奇数且取值小于 $30$ ，坐标 $x，y$ 取值均从 $0$ 开始，敌营左下角定义为 $(0,0)$,右上角定义为 $(n-1,n-1)$.

2.敌营入口在坐标 $(0,n/2)$，敌军司令部在坐标 $(n-1，n/2)$。

3.游戏角色的行动方向只包含上、下、左、右四个方向，即一次行动 $x、y$ 坐标不可同时变化。

4.在没有满足题目要求的可达路径时，需要返回{$0,0$}。

2026 华为OD机试真题 4月8日华为OD上机新系统考试真题 200 分题型

输入描述

参数 $1$，敌军阵营的边长 $n$ 。

参数 $2$，哨兵位置列表 $Point${$x，y，x$表示行坐标，$y$ 表示列坐标。

输出描述

两个成员的数组，第一个成员为最短路径条数，第二个成员为最短路径长度

示例1

输入

3,[(1,1)]

输出

[0,0]

说明

无路径场景，S 表示哨兵位置，A 表示起点，E 表示终点，哨兵警戒了全图

/无可达路径，因此返回为{0，0}

示例2

输入

5,[(2,1)]

输出

[1,7]

说明

单一最短路径场景，S 表示哨兵位置，A 表示起点，E 表示终点

最短路径:[(0,2),(0,3),(1,3),(2,3),(3,3),(4,3),(4,2)][(0,2),(0,3),(1,3),(2,3),(3,3),(4,3),(4,2)]

因此返回值为{1，7}

示例3

输入

5,[(2,2)]

输出

[2,9]

说明

两条最短路径，S 表示哨兵位置，A 表示起点，E* 表示终点

路径1:[(0,2),(0,1),(0,0),(1,0),(2,0),(3,0),(4,0),(4,1),(4,2)][(0,2),(0,1),(0,0),(1,0),(2,0),(3,0),(4,0),(4,1),(4,2)]

路径2:[(0,2),(0,3),(0,4),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2)][(0,2),(0,3),(0,4),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2)]

因此返回值为{2,9}

解题思路

核心思想

题目要求在 $n \times n$ 的网格中寻找从入口 $(0, n/2)$ 到司令部 $(n-1, n/2)$ 的最短路径条数及长度。

关键点如下：

1. 哨兵警戒区：每个哨兵位于 $(x, y)$，其警戒范围是以其为中心的 $9$ 宫格。这意味着坐标在 $[x-1, x+1]$ 和 $[y-1, y+1]$ 范围内的所有点都是不可通行的障碍物。
2. 网格坐标：入口在 $(0, n/2)$，司令部在 $(n-1, n/2)$。坐标系规定左下角为 $(0,0)$，右上角为 $(n-1, n-1)$。
3. 路径长度定义：根据示例分析，路径长度指的是路径上点的个数（即 步数 + 1）。
4. 算法选择：
   • BFS (广度优先搜索) 是寻找无权图（或等权图）最短路径的最佳选择。
   • 在 BFS 过程中，我们需要同时维护两个信息：
     • dist[x][y]：从起点到点 $(x, y)$ 的最短距离。
     • count[x][y]：从起点到点 $(x, y)$ 的最短路径条数。
5. BFS 逻辑：
   • 初始化 dist 为无穷大，count 为 0。
   • 起点 dist[start] = 1（按点数算），count[start] = 1。
   • 对于当前点 $(x, y)$ 的邻居 $(nx, ny)$：
     • 如果 dist[nx][ny] > dist[x][y] + 1：说明找到了更短的路径，更新 dist[nx][ny] = dist[x][y] + 1，并令 count[nx][ny] = count[x][y]。
     • 如果 dist[nx][ny] == dist[x][y] + 1：说明找到了另一条相同长度的最短路径，累加计数 count[nx][ny] += count[x][y]。

复杂度分析

• 时间复杂度：$O(n^2)$。我们需要预处理所有哨兵的警戒范围，并进行一次 BFS 遍历。由于 $n < 30$，网格大小最多为 $900$ 个点。
• 空间复杂度：$O(n^2)$。用于存储网格的障碍物信息、距离数组和路径计数