约定
\(K\) 维空间中，整点的坐标以 \(K\) 个整数表示，形如
\[Point\left(X_1,X_2,\cdots,X_k\right)
\]
定义两个点的曼哈顿距离为 每一维坐标差的绝对值之和，记为
\[MD\left(A, B\right) = \sum_{i=1}^{K} \left|{X_{i_A}-X_{i_B}}\right|
\]
定义两个点 \(A\) , \(B\) 相邻 当且仅当满足
\[MD\left(A, B\right) = 1
\]
最短路径计数
每次只能移动到相邻的点，容易发现 \(S\) 到 \(T\) 的曼哈顿距离最短路径可能经过的点构成了一个 \(K\) 维方体，而 \(S\) 和 \(T\) 正为此方体相对的两个顶点。
三维空间中示意图如下：
我们定义在第 \(i\) 维坐标上 \(\pm 1\) 为操作 \(i\)，显然的是，需要什么操作及具体个数是已知的，总数为
\[MD\left(S,T\right)
\]
那么一条路径就可以转换成一个操作序列，不同的路径数量等价于本质不同的序列数量。
两个序列本质不同当且仅当至少存在一个位置上的操作编号不同。
显然在排列中，同样的操作本质不同，但实际上，它们是相同的，所以需要去重。
则总方案数为
\[\frac{MD\left(S,T\right)!}{\Pi_{i=1}^{K} \left(\left|{X_{i_S}-X_{i_T}}\right|!\right)}
\]
扩展
假定在此 \(K\) 维空间中，存在一些整点是不能经过的（保证不为 \(S\) 和 \(T\)），那么 \(S\) 到 \(T\) 的最短路径数量会有什么变化呢？
我们称不能经过的点为 标记点
并定义两个点之间不经过标记点的最短路径条数为
\[AMDC\left(A,B\right)
\]
在不考虑标记点时，
\[AMCD\left(A, B\right) = \frac{MD\left(A,B\right)!}{\Pi_{i=1}^{K} \left(\left|{X_{i_A}-X_{i_B}}\right|!\right)}
\]
同时令
\[f_i=AMDC\left(S,i\right)
\]
显然，真正对我们有用的只有 \(K\) 维方体内的标记点和 \(T\) 点的 \(f\) 值，考虑 \(DP\) 转移。
那么，\(A\) 点对 \(B\) 点的 \(f\) 造成影响的充要条件是什么？
可以发现为
\[x_{i_A} \le x_{i_B} \left( x | x \in \left[ 1,K \right] \right)
\]
也就是 \(K\) 维偏序。
所以
\[f_i = AMDC\left( S, i \right) - \sum_{j} g\left(j, i\right) \times f_j \times AMDC\left(j, i\right)
\]
其中，
\[g\left(A, B\right) = \left\{ \begin{aligned} 1 \qquad& x_{i_A} \le x_{i_B} \left( x | x \in \left[ 1,K \right] \right)\\ 0 \qquad& other \end{aligned}\right.
\]
满足 \(g\left(S, T\right) = 1\)
用到了一点小容斥。
可以画一下二维空间中的图来帮助理解。
如有任何问题请私信作者 @qkhm