在不接触阴影方块的情况下移动网格

Question

两个相邻顶点之间的每个线段的长度为 1 个单位。有多少种方法可以沿着 10 段序列从 A 到 B 而不接触阴影正方形的边或顶点？

我知道答案是 72，但正在努力寻找如何得出该答案。

Answer 1

到达 (0,k) 或 (k,0) 的方式数为 1。 当 x >= 1, y >= 1 时到达 (x,y) 的方式数为 way(x-1, y) + 方式(x, y-1)。填入顶行和左列，按此公式逐行填入值。将接触阴影方块的顶点视为 way() 为零。

1   1   1   1   1   1
1   2   0   0   1   2
1   3   0   0   1   3
1   4   4   4   5   8
1   5   9  13  18  26
1   6  15  28  46  72