U636459 网格

网格走路问题的多维版本。

我们说过，如果网格是二维的，复杂度可以做到 \(\sqrt {nm}\)，这是因为通过根号分治有 DP 和容斥的两种解法，这里都需要运用到。

将所有坏点排序之后 DP 即可。