目录
题目
思路
Code
题目
题目内容：
一个封闭迷宫有 n 个房间，编号为 0 到 n-1，相邻房间由双向门连接。
玩家 A 可以自由移动，玩家 B 沿给定路径来回巡逻。
请为玩家 A 选择最优移动策略，使 A 和 B 在最少回合后相遇。
注意：A 和 B 初始出发点不同。
规则：
每回合，A 可以移动到相邻房间，也可以停留在当前房间。
B 按给定路径循环移动：从起点开始，每回合移动到路径下一个位置；到达路径末端后折返，回到起点后再折返，如此循环往复。
B 在端点处不额外停留。例如单程路径 [0,1,2]，B 的完整位置序列为 [0,1,2,1,0,1,2,1,...]。
A 和 B 在某回合结束后位于同一房间，视为相遇。
输入描述：
输入为一行字符串，格式为：
n,edges,startA,patrolPath
n 表示房间数量，1 < n < 100。
edges 表示房间连接关系，是 int 型二维数组，例如 [[0,1],[1,2],[2,3],[3,4]]，表示双向连通；空数组 [] 表示没有连接。
startA 表示 A 的初始房间编号。
patrolPath 表示 B 的巡逻路径，即一次单程路径，例如 [0,1,2] 表示 B 从 0 出发，经过 1 到达 2，然后原路返回。patrolPath 至少包含一个元素，只有一个元素时表示 B 原地不动。
输出描述：
输出一个整数，表示 A 和 B 相遇的最小回合次数。
若无法相遇，输出 -1。
样例1输入：
5,[[0,1],[1,2],[2,3],[3,4]],4,[0,1,2,3,4]
样例1输出：
2
样例1说明：
线性迷宫中，A 从 4 出发，B 从 0 出发。
第 1 回合后，A 可到 3，B 到 1。
第 2 回合后，A 可到 2，B 到 2，二者相遇。
样例2输入：
8,[[0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,5]],0,[5,6,7,5]
样例2输出：
6
样例2说明：
B 的完整巡逻位置为 5,6,7,5,7,6,5,...
A 从 0 出发，最早可在第 6 回合于房间 5 与 B 相遇。
样例3输入：
3,[],0,[1]
样例3输出：
-1
样例3说明：
迷宫房间之间没有连接，A 无法到达 B 所在房间。
样例4输入：
3,[[0,2]],0,[2]
样例4输出：
1
样例4说明：
B 原地不动，A 第 1 回合移动到房间 2 后相遇。
思路
BFS
先从 A 的起点对无向图做 BFS，得到 A 到每个房间的最短回合数 dist。
然后将 B 的单程巡逻路径展开成循环序列。例如 [0,1,2] 展开为一个周期 [0,1,2,1]，之后按周期循环。
若 B 在周期中的第 k 个位置为 room，周期长度为 C，那么 B 会在所有满足 t % C = k 的回合位于 room。
只要 dist[room] <= t，A 就可以先移动到 room，再通过停留等待 B 到达。
枚举 B 周期中的每个位置，计算不小于 dist[room] 且至少为 1 的最小合法回合 t，取最小值。
如果 B 的所有巡逻房间对 A 都不可达，则输出 -1。
Code
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Queue; public class Main { static class Parser { String s; int index; Parser(String s) { this.s = s; } void skipSpaces() { while (index < s.length() && Character.isWhitespace(s.charAt(index))) { index++; } } void skipComma() { skipSpaces(); if (index < s.length() && s.charAt(index) == ',') { index++; } skipSpaces(); } int parseInt() { skipSpaces(); int sign = 1; if (s.charAt(index) == '-') { sign = -1; index++; } int value = 0; while (index < s.length() && Character.isDigit(s.charAt(index))) { value = value * 10 + s.charAt(index) - '0'; index++; } skipSpaces(); return value * sign; } int[] parse1DArray() { // 输入里数组直接嵌在一行中，手写解析可以兼容空数组和嵌套数组。 skipSpaces(); List<Integer> list = new ArrayList<>(); index++; skipSpaces(); while (index < s.length() && s.charAt(index) != ']') { list.add(parseInt()); skipSpaces(); if (index < s.length() && s.charAt(index) == ',') { index++; } skipSpaces(); } index++; int[] arr = new int[list.size()]; for (int i = 0; i < list.size(); i++) { arr[i] = list.get(i); } return arr; } int[][] parse2DArray() { skipSpaces(); List<int[]> list = new ArrayList<>(); index++; skipSpaces(); while (index < s.length() && s.charAt(index) != ']') { list.add(parse1DArray()); skipSpaces(); if (index < s.length() && s.charAt(index) == ',') { index++; } skipSpaces(); } index++; return list.toArray(new int[list.size()][]); } } static int minMeetRounds(int n, int[][] edges, int startA, int[] patrolPath) { List<List<Integer>> graph = new ArrayList<>(); // 房间门是双向的，先建邻接表方便 BFS 求最短距离。 for (int i = 0; i < n; i++) { graph.add(new ArrayList<>()); } for (int[] edge : edges) { graph.get(edge[0]).add(edge[1]); graph.get(edge[1]).add(edge[0]); } int inf = 1_000_000_000; int[] dist = new int[n]; Arrays.fill(dist, inf); Queue<Integer> q = new ArrayDeque<>(); dist[startA] = 0; q.offer(startA); while (!q.isEmpty()) { // BFS 得到 A 到每个房间的最早到达回合。 int u = q.poll(); for (int v : graph.get(u)) { if (dist[v] == inf) { dist[v] = dist[u] + 1; q.offer(v); } } } List<Integer> cycle = new ArrayList<>(); for (int room : patrolPath) { cycle.add(room); } for (int i = patrolPath.length - 2; i >= 1; i--) { cycle.add(patrolPath[i]); } int best = inf; int c = cycle.size(); for (int k = 0; k < c; k++) { // 枚举 B 在周期中的位置，计算 A 能等到它的最早回合。 int room = cycle.get(k); if (dist[room] == inf) { continue; } int need = Math.max(1, dist[room]); int cand = k >= need ? k : k + ((need - k + c - 1) / c) * c; best = Math.min(best, cand); } return best == inf ? -1 : best; } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input = br.readLine(); Parser parser = new Parser(input); int n = parser.parseInt(); parser.skipComma(); int[][] edges = parser.parse2DArray(); parser.skipComma(); int startA = parser.parseInt(); parser.skipComma(); int[] patrolPath = parser.parse1DArray(); System.out.println(minMeetRounds(n, edges, startA, patrolPath)); } }Go
package main import ( "bufio" "encoding/json" "fmt" "os" "strconv" "strings" ) func minMeetRounds(n int, edges [][]int, startA int, patrolPath []int) int { // 先建双向邻接表，再用 BFS 计算 A 到各房间的最早到达时间。 graph := make([][]int, n) for _, e := range edges { graph[e[0]] = append(graph[e[0]], e[1]) graph[e[1]] = append(graph[e[1]], e[0]) } const inf = int(1e9) dist := make([]int, n) for i := range dist { dist[i] = inf } q := []int{startA} dist[startA] = 0 for len(q) > 0 { // BFS 按回合层层扩展，第一次到达的距离就是最短回合数。 u := q[0] q = q[1:] for _, v := range graph[u] { if dist[v] == inf { dist[v] = dist[u] + 1 q = append(q, v) } } } cycle := append([]int{}, patrolPath...) // B 到端点后立即折返，周期只需要补上中间段的反向路径。 for i := len(patrolPath) - 2; i >= 1; i-- { cycle = append(cycle, patrolPath[i]) } best := inf c := len(cycle) for k, room := range cycle { // 枚举 B 在周期中的位置，计算 A 能等到它的最早回合。 if dist[room] == inf { continue } need := dist[room] if need < 1 { need = 1 } cand := 0 if k >= need { cand = k } else { cand = k + ((need-k+c-1)/c)*c } if cand < best { best = cand } } if best == inf { return -1 } return best } func main() { reader := bufio.NewReader(os.Stdin) line, _ := reader.ReadString('\n') line = strings.TrimSpace(line) parts := strings.SplitN(line, ",", 2) n, _ := strconv.Atoi(strings.TrimSpace(parts[0])) var parsed []interface{} if err := json.Unmarshal([]byte("["+parts[1]+"]"), &parsed); err != nil { fmt.Println(-1) return } edgesRaw := parsed[0].([]interface{}) edges := make([][]int, len(edgesRaw)) for i, item := range edgesRaw { pair := item.([]interface{}) edges[i] = []int{int(pair[0].(float64)), int(pair[1].(float64))} } startA := int(parsed[1].(float64)) pathRaw := parsed[2].([]interface{}) patrolPath := make([]int, len(pathRaw)) for i, item := range pathRaw { patrolPath[i] = int(item.(float64)) } fmt.Println(minMeetRounds(n, edges, startA, patrolPath)) }C
#include <ctype.h> #include <limits.h> #include <stdio.h> #include <string.h> #define MAXN 105 #define MAXE 10005 #define INF 1000000000 typedef struct { char s[20000]; int index; } Parser; int head[MAXN], to[MAXE * 2], nxt[MAXE * 2], edgeCnt; void addEdge(int u, int v) { to[edgeCnt] = v; nxt[edgeCnt] = head[u]; head[u] = edgeCnt++; } void skipSpaces(Parser* p) { while (p->s[p->index] && isspace((unsigned char)p->s[p->index])) { p->index++; } } void skipComma(Parser* p) { skipSpaces(p); if (p->s[p->index] == ',') { p->index++; } skipSpaces(p); } int parseInt(Parser* p) { skipSpaces(p); int sign = 1; if (p->s[p->index] == '-') { sign = -1; p->index++; } int value = 0; while (isdigit((unsigned char)p->s[p->index])) { value = value * 10 + p->s[p->index] - '0'; p->index++; } skipSpaces(p); return value * sign; } int parse1DArray(Parser* p, int arr[]) { // 输入里数组直接嵌在一行中，手写解析可以兼容空数组和嵌套数组。 skipSpaces(p); int count = 0; p->index++; skipSpaces(p); while (p->s[p->index] && p->s[p->index] != ']') { arr[count++] = parseInt(p); skipSpaces(p); if (p->s[p->index] == ',') { p->index++; } skipSpaces(p); } p->index++; return count; } void parseEdges(Parser* p) { skipSpaces(p); p->index++; skipSpaces(p); while (p->s[p->index] && p->s[p->index] != ']') { int pair[2]; parse1DArray(p, pair); addEdge(pair[0], pair[1]); addEdge(pair[1], pair[0]); skipSpaces(p); if (p->s[p->index] == ',') { p->index++; } skipSpaces(p); } p->index++; } int minMeetRounds(int n, int startA, int patrolPath[], int pathLen) { int dist[MAXN]; int q[MAXN]; for (int i = 0; i < n; i++) { dist[i] = INF; } int front = 0, back = 0; dist[startA] = 0; q[back++] = startA; while (front < back) { // BFS 得到 A 到每个房间的最早到达回合。 int u = q[front++]; for (int e = head[u]; e != -1; e = nxt[e]) { int v = to[e]; if (dist[v] == INF) { dist[v] = dist[u] + 1; q[back++] = v; } } } int cycle[MAXN * 2]; int c = 0; for (int i = 0; i < pathLen; i++) { cycle[c++] = patrolPath[i]; } for (int i = pathLen - 2; i >= 1; i--) { // B 到端点后立即折返，周期只需要补上中间段的反向路径。 cycle[c++] = patrolPath[i]; } int best = INF; for (int k = 0; k < c; k++) { // 枚举 B 在周期中的位置，计算 A 能等到它的最早回合。 int room = cycle[k]; if (dist[room] == INF) { continue; } int need = dist[room] > 1 ? dist[room] : 1; int cand = k >= need ? k : k + ((need - k + c - 1) / c) * c; if (cand < best) { best = cand; } } return best == INF ? -1 : best; } int main() { Parser p; if (fgets(p.s, sizeof(p.s), stdin) == NULL) { return 0; } p.index = 0; memset(head, -1, sizeof(head)); edgeCnt = 0; int n = parseInt(&p); skipComma(&p); parseEdges(&p); skipComma(&p); int startA = parseInt(&p); skipComma(&p); int patrolPath[MAXN]; int pathLen = parse1DArray(&p, patrolPath); printf("%d\n", minMeetRounds(n, startA, patrolPath, pathLen)); return 0; }【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集
【华为od机试真题Python】：Python真题题库
【华为od机试真题JavaScript】：JavaScript真题题库
【华为od机试真题Java&Go】：Java&Go真题题库
【华为od机试真题C++】：C++真题题库
【华为od机试真题C语言】：C语言真题题库
【华为od面试手撕代码题库】：面试手撕代码题库
【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】
华为OD机试:二本院校有机会吗?
有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。
