algorithm - 计算从正方形中心到边缘的路径

Question

假设我有一个大小为 (2n+1)x(2n+1) 的正方形，对于一些 n，即一个边长奇数的正方形。
从最中心的单元格开始，我有兴趣计算编号。到达任意边缘单元的方式（如下图所示）。
只允许不重叠的路径，即如果一个单元格已经被访问过，我们就不能重新访问它。

下图显示了一个边长为 9（n=4）的正方形和两条长度为 5 的可能路径。

我认为所有路径的长度范围都是：[n to (2n-1)^2+1 ]
计数没有。路径长度：
1 - 0
2 - 0
3 - 0
4 - 4
5 - 32
6 - ...？
但是随着路径长度的增加，我似乎无法解开所有的可能性。我知道对称性在这里起作用，但是有没有结构化的方法来计算所有路径？

谢谢，

Answer 1

要查找从方板中心开始并在边界处结束的路径，您可以使用经过调整的 DFS（深度优先搜索），您将在其中存储已经访问过的图块，这样您就不会再踩到它们了。

董事会确实有很多对称性。您只需注意以下几点即可将搜索到的路径数除以 4：

• 从中心开始，你可以去Up , Down , Left , Right
• 所有开始走向Up的路径通过旋转生成所有其他以Down、Left、Right开始的路径

一旦你这样做了，你可以进一步注意到：

• 一旦你走了U，你就可以走了U，L或者R
• 你走时产生的所有路径都是镜像对称L时产生的相同路径。R

您可以重复几次，直到到达正方形的边界。从 go 开始的全部路径U将是：

• U-U-U-U（一个路径）
• 2 次路径以U-U-U-L
• 2 次路径以U-U-L
• 2 次路径以U-L

一旦你计算了这些，你就可以乘以四得到全部的路径。