这题本质是一个 网格最短路 + 最短路条数统计 问题,适合用 BFS(广度优先搜索) 来做。
n * n 的矩阵。(0, n / 2),终点是 (n - 1, n / 2)。小王在玩一款叫做直捣黄龙的小游戏,在该游戏中他需要从入口位置进入敌营,绕过哨兵的层层封锁,达到敌军司令部实施斩首行动。
敌军阵营是一个 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