c++ - 通过 m x n 网格的游览次数？

Question

令 T(x,y) 为 X × Y 网格上的游览次数，使得:

1. 游览从左上角的方 block 开始
2. 游览包括向上、向下、向左或向右移动一格，
3. 游览恰好访问每个方格一次，并且
4. 导览在左下方的方 block 处结束。

例如，很容易看出 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)

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

这适用于小型电路板。真正的乐趣始于更大的棋盘，你必须在树上剪下无法解决的 Twig (例如:有一个无法到达的未访问单元格区域)。