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

Question

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

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

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

谢谢，

Answer 1

要找到从方 block 中心开始到边界结束的路径，您可以使用经过调整的 DFS (Depth First Search)，您将在其中存储已经访问过的图 block ，这样您就不会再次踩到它们。

棋盘上确实有很多对称性。您可以将搜索路径的数量除以 4，只需注意:

• 从中心开始，你可以去Up，Down，左左，右右
• 所有从Up 开始的路径生成所有其他从Down 开始的路径， Left, Rright 旋转

一旦你这样做了，你可以通过注意到以下内容走得更远:

• 一旦你去了U，你就可以去U，L 或 R
• 通过镜像对称，当你走 L 时生成的所有路径与你走 R 时生成的路径相同.

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

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

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