直接建图然后 bfs 是 O(n4)O(n^4)O(n4) 的,因为有 O(n3)O(n^3)O(n3) 个点,每次拓展时需要枚举同轴的 O(n)O(n)O(n) 个点。
注意到同一条轴线上的点一定按奇偶性被分为了两类,每个类内部都是一个团,可以在一步之内互相到达。不难想到对三个方向的 O(n2)O(n^2)O(n2) 条轴线各自开一个桶表示这条轴线上的团是否被到达过,这样就可以快速剪掉重复的判断。复杂度降至 O(n3)O(n^3)O(n3),可以通过本题。
使用您的 Hydro 通用账户