每步移动都是上下左右,我们可以分别用字母UDLR来代替,
那么每个合法的移动都将构成一个长度为k的序列(UDLR构成),
这个序列中,U比D多n,R比L多m
如果记UDLR的数目分别为udlr,那么
u=d+n,
r=l+m
u+d+l+r=k
也就是
2(d+l)=k-(m+n)
对于每个满足这个方程的d和l,我们都可以求出对应的u,r
比如
d=0, l=(k-(m+n))/2, u=n, r=(k-(m+n))/2+m
d=1, l=(k-(m+n))/2-1, u=n+1, r=(k-(m+n))/2+m-1
...
而对于每一种知道了u,d,l,r的情况,U,D,L,R序列的数目(它们所在位置可能不同)
是(u+d+l+r)!/(u!d!r!l!)