c++ - 通过 mxn 网格的游览次数？

Question

令 T(x,y) 为 X × Y 网格上的旅行次数，使得：

1. 游览从左上角的广场开始
2. 巡回赛由上、下、左或右一格的移动组成，
3. 游览每个广场只访问一次，并且
4. 游览在左下角的广场结束。

很容易看出，例如，T(2,2) = 1, T(3,3) = 2, T(4,3) = 0 和 T(3,4) = 4。 编写一个程序计算 T(10,4)。

• 我已经为此工作了好几个小时......我需要一个程序，将网格的尺寸作为输入并返回可能的旅行次数？关于我应该如何解决这个问题的任何想法？

Answer 1

由于您是回溯的新手，这可能会让您知道如何解决这个问题：

您需要一些数据结构来表示网格上单元格的状态（已访问/未访问）。

你的算法：

step(posx, posy, steps_left)
    if it is not a valid position, or already visited
        return
    if it's the last step and you are at the target cell
        you've found a solution, increment counter
        return
    mark cell as visited             
    for each possible direction:
       step(posx_next, posy_next, steps_left-1)
    mark cell as not visited

并运行

step(0, 0, sizex*sizey)

回溯的基本构建块是：评估当前状态、标记、递归步骤和取消标记。

这适用于小板。真正的乐趣从更大的木板开始，您必须在树上切割无法解决的树枝（例如：有一个无法到达的未访问单元格区域）。

Answer 2

分配的练习是一个很好的练习。它迫使您逐步思考几个概念。我无法为您考虑所有概念，但也许我可以通过提出以下问题来提供帮助。

在某些时候，您的程序必须代表部分完成的游览。 也就是说，它必须表示一条尚未通过所有方格且尚未到达其左下角目标的路径，但如果该路径后来被扩展，则它可能会同时完成这两个目标。你是什​​么意思代表一个部分完成的旅行？

如果你能回答这个问题，并且如果你掌握了递归的概念，那么人们怀疑你可以通过一些工作来解决这个问题，但没有太多真正的麻烦。代表部分完成的旅行是你的障碍，所以我的建议是你去努力。

更新： 见下面@KarolyHorvath 的评论。如果你还没有学会动态分配内存的使用（或者，等价的，像 std::vector 和 std::list 这样的 STL 容器），那么你应该听从他的提示，这在任何情况下都是一个很好的提示。