题解

思路

把每间藏宝宫室看成一个有向图结点，传送门允许的移动看成有向边。一个强连通分量内部的所有结点都可以在一次行走中全部经过；缩点后得到有向无环图，问题转化为结点权值为强连通分量所含藏宝宫室数的最长路。

直接从每扇横天门向同行所有藏宝宫室连边、从每扇纵寰门向同列所有藏宝宫室连边，最坏会产生平方级边数。为压缩这些完全连接关系，对每个出现过藏宝宫室的行建立一个行结点，对每个出现过藏宝宫室的列建立一个列结点。行结点向该行全部藏宝宫室连边，横天门只需向所属行结点连一条边；列结点同理。任意门至多检查周围八个坐标，可用坐标哈希表查找目标藏宝宫室。

做法

1. 离散化所有出现的行号和列号，为每个不同行、列建立一个权值为零的辅助结点。
2. 对每间藏宝宫室，从其行辅助结点和列辅助结点分别向它连边；再按传送门类型连向所属行结点、所属列结点或八邻域中存在的藏宝宫室。
3. 求整个压缩图的强连通分量。每个分量的权值等于其中真实藏宝宫室结点的数量，辅助结点不计数。
4. 建立缩点后的有向无环图，按拓扑顺序进行最长路动态规划。由于可以从任意宫室进入，所有分量都可以作为起点。

正确性证明

行辅助结点只接收同行横天门的边，并向该行所有藏宝宫室连边，因此经过两条压缩边恰好等价于一次横天门传送，且不会引入其他移动。列辅助结点同理。任意门边按八邻域坐标逐一建立，所以压缩图中的真实宫室可达关系与原题完全一致。

在同一个强连通分量内，从任意结点出发都能到达分量内任意其他结点，并能继续到达预定的离开边，因此一次行走可以收集该分量内全部藏宝宫室。缩点图没有环，一条行走经过的强连通分量必然形成其中的一条有向路径；反过来，任意一条缩点路径都能在每个分量内收集全部藏宝宫室后沿对应边进入下一个分量。因此答案恰好是缩点图上的最大结点权路径和。

复杂度

• 时间复杂度：$O(N\log N)$，其中行列离散化需要排序，其余建图、强连通分量和最长路均为线性规模。
• 空间复杂度：$O(N)$。