1 条题解

  • 0
    @ 2026-11-15 20:48:23

    题目分析

    注意到迷宫在以 nn 为周期变化,所以可以把一个周期内的迷宫情况预处理好。我们需要知道抵达一个位置时是在迷宫的那个状态,因此可以把每个位置拆成 nn 个点,计算在模 nn 为 rr 的时间到达 (x,y)(x,y) 所需最少时间,则可以在新建的以 (r,x,y)(r,x,y) 为点的图上 BFS 计算最短路。

    需要注意一些细节,例如对于一般的格子,必须今天没有墙且今晚不会有墙到,才能走过去;而终点则只要求今天没有墙就可以走过去。

    总复杂度 O(n3)O(n^3),可以通过全部测试数据。需要适当注意内存的使用。

    • 1

    信息

    ID
    184
    时间
    3000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    6
    已通过
    1
    上传者