目录题目思路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,patrolPathn 表示房间数量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 可到 3B 到 1。第 2 回合后A 可到 2B 到 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] tA 就可以先移动到 room再通过停留等待 B 到达。枚举 B 周期中的每个位置计算不小于 dist[room] 且至少为 1 的最小合法回合 t取最小值。如果 B 的所有巡逻房间对 A 都不可达则输出 -1。Codeimport 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(); ListInteger 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(); Listint[] 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) { ListListInteger 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); QueueInteger 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); } } } ListInteger 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)); } }Gopackage 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-kc-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机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗?有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。
