AlgoMooc
你已开通华为OD训练营权益,还差最后一步——完成入营激活(兑换课程 + 加飞书 + 登记服务群),即可解锁全部课程与专属服务。去激活 →
← 返回题库

N0005. 0408-直捣黄龙

困难通过率 34% · 提交 95 · 通过 32
BFS图论最短路

(暂无题目描述)

输入描述

小王在玩一款叫做"直捣黄龙"的小游戏,在该游戏中他需要从入口位置进入敌营,绕过哨兵的层层封锁,到达敌军司令部实施斩首行动。 敌军阵营是一个 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}

输出描述

- 参数1:敌军阵营的边长 n - 参数2:哨兵位置列表 Point{x, y},x 表示行坐标,y 表示列坐标

示例

示例 1

输入

3
1
1 1

输出

0 0

说明:无路径场景,S表示哨兵位置,A表示起点,E表示终点,哨兵警戒了全图 无可达路径,因此返回为 {0, 0} 矩阵图: 0 0 0 A S E 0 0 0

示例 2

输入

5
1
2 1

输出

1 7

说明:单一最短路径场景,S表示哨兵位置,A表示起点,E表示终点 最短路径: [(0,2), (0,3), (1,3), (2,3), (3,3), (4,3), (4,2)] 因此返回值为 {1, 7} 矩阵图: 0 0 0 0 0 0 0 0 0 0 A 0 0 0 E 0 0 S 0 0 0 0 0 0 0

示例 3

输入

5
1
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)] 路径2: [(0,2), (0,3), (0,4), (1,4), (2,4), (3,4), (4,4), (4,3), (4,2)] 因此返回值为 {2, 9} 矩阵图: 0 0 0 0 0 0 0 0 0 0 A 0 S 0 E 0 0 0 0 0 0 0 0 0 0

时间限制 1000 ms · 内存限制 128 MB

写完代码点「提交」,将对全部测试用例判题。

向老师提问

针对「0408-直捣黄龙」把疑问、代码和报错填清楚,老师收到后能更快、更准地回复你。