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

Question

假设我有一个大小为(2n+1)x(2n+1)的正方形，对于某个n，即边长为奇数的正方形。

从最中心的单元格开始，我感兴趣的是计算no。到达任何边缘单元的方式(如下图所示)。

只允许不重叠的路径，也就是说，如果一个单元已经被访问过，我们就不能重新访问它。

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

​

​

我认为所有路径的长度范围是:n到(2n-1)^2+1

数不到。长度的路径数：

1-0

2-0

3-0

4-4

5- 32

6- ...？

但随着路径长度的增加，我似乎无法展开所有的可能性。我知道对称性在这里起作用，但是有没有任何结构化的方法来计算所有的路径？

谢谢,

Answer 1

要找到从正方形棋盘中心开始并在边框结束的路径，您可以使用调整后的DFS (Depth First Search)，在这里您将存储已经访问过的磁贴，这样您就不会再次踩到它们。

董事会确实有很大的对称性。只需注意以下几点，就可以将搜索路径的数量除以4：

从中心开始，你可以去开始的路径，U**p生成所有其他开始的路径，从D**own，L**eft，开始，

• R**ight by rotation

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

当你去U，时，你可以去U，L或R

• All路径，当你去L时生成的路径与你通过镜像对称去R时生成的路径是一样的。
• 一旦你走了，你就可以走了。

您可以重复此操作几次，直到到达正方形的边界。从U开始的完整路径数量为：

• U-U-U-U (一条路径)以U-U-U-L
• 2开头的路径乘以U-U-L
• 2开头的路径乘以U-L

开头的路径

• 2倍

一旦你计算了这些，你就可以通过乘以4得到完整的路径数量。