题意题目链接分析先考虑没有障碍怎么做，定义 f(i,j,k) 每一维走了 i,j,k 位的方案数，转移乘个组合数即可。现在多了一些障碍，考虑容斥。实际我们走过的点都有严格的大小关系，所以先把所有障碍点按维度排序，然后定义 g(i,j) 表示走到 i 这个障碍点，走了 j 个障碍点的方案数，利用 f 转移。实际第二维在转移时乘以-1就可以忽略。复杂度 \(O(o^2)\)开始写的刷表发现有问题，因为刷表时的所有状态都和 (n,m,r) 有关，所以中间的状态不能表示和终态一样的意义。代码代码链接