本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-07 14:31:12

我们设 $f(x, y, S)$ 表示当前在 $(x, y)$，包含了的宝藏是 $S$，最少的移动步数。那么答案是 $\max val_S - f(x, y, S)$。

考虑转移。前两维的转移是简单的。由于转移顺序不确定，可以最短路。后面的 $S$ 怎么动态维护？

计算几何中的射线法，可以用来判断某个点是否在某个多边形中。具体的方法是：从这个点做一条直线，看其经过这个多边形的多少条边。如果经过奇数条即是在内，否则在外。我们可以沿用相同的方法，每次转移时从每个宝藏平行向右做一条直线，看是否和新扩展出的点交。若交了，则其在 $S$ 中取异或。

这样用最短路转移即可。