解题思路
本题在 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) 时:
- 若 (nx,ny) 首次被访问,则
dist[nx][ny]=dist[x][y]+1,ways[nx][ny]=ways[x][y];