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

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

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

• 从中心开始，您可以Up、Down、左左，右右
• 所有以 Up 开头的路径都会生成以 Down 开头的所有其他路径， 左左、右右通过旋转

完成此操作后，您可以进一步注意:

• 离开U后，您可以前往U、L 或 R
• 走L时生成的所有路径与走R时通过镜像对称生成的路径相同.

您可以重复此操作几次，直到到达方 block 的边界。从 U 开始的路径总数将为:

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

计算完这些后，乘以四即可得到全部路径。