Status
Development
Support
- 京ICP备2025123107号-1
- Worker 1, 25ms
- Powered by Hydro v5.0.0-beta.18 Community
本题在 n×n 网格上，从固定起点 (0,n/2) 走到固定终点 (n−1,n/2)，四向移动。每个哨兵 (gx,gy) 会使切比雪夫距离 max(∣x−gx∣,∣y−gy∣)≤1 的格子全部不可走（即以其为中心的 3×3 九宫格并到禁区集合里）。
算法上这是无权图最短路问题：把每个可走格子看作顶点，四邻边权为 1。用 BFS 求从起点到终点的最短边数；若不可达返回 [0,0]。
在统计最短路径条数时，在 BFS 松弛过程中维护 ways[x][y]：从起点到 (x,y) 的最短路条数。当从 (x,y) 扩展到邻居 (nx,ny) 时：
dist[nx][ny]=dist[x][y]+1，ways[nx][ny]=ways[x][y]；小王在玩一款叫做直捣黄龙的小游戏，在该游戏中他需要从入口位置进入敌营，绕过哨兵的层层封锁，达到敌军司令部实施斩首行动。
敌军阵营是一个 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 表示列坐标。
两个成员的数组，第一个成员为最短路径条数，第二个成员为最短路径长度。
输入
3,[(1,1)]
输出
[0,0]
说明
//无路径场景，S 表示哨兵位置，A 表示起点，E 表示终点，哨兵警戒了全图
//无可达路径，因此返回为{0，0}
//矩阵图如下:
0 0 0
A S E
0 0 0
输入
5,[(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
输入
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)]
//路径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