注意到迷宫在以 nnn 为周期变化,所以可以把一个周期内的迷宫情况预处理好。我们需要知道抵达一个位置时是在迷宫的那个状态,因此可以把每个位置拆成 nnn 个点,计算在模 nnn 为 rrr 的时间到达 (x,y)(x,y)(x,y) 所需最少时间,则可以在新建的以 (r,x,y)(r,x,y)(r,x,y) 为点的图上 BFS 计算最短路。
需要注意一些细节,例如对于一般的格子,必须今天没有墙且今晚不会有墙到,才能走过去;而终点则只要求今天没有墙就可以走过去。
总复杂度 O(n3)O(n^3)O(n3),可以通过全部测试数据。需要适当注意内存的使用。
使用您的 Hydro 通用账户