0

令 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)。

我已经为此工作了好几个小时......我需要一个程序，将网格的尺寸作为输入并返回可能的旅行次数？

我已经为此工作了好几个小时......我需要一个程序，将网格的尺寸作为输入并返回可能的旅行次数？

我写了这段代码来解决这个问题......我似乎无法弄清楚如何检查所有方向。

#include <iostream>

int grid[3][3];
int c = 0;

int main(){    
    solve (0, 0, 9);
}

int solve (int posx, int posy, steps_left){
    if (grid[posx][posy] = 1){
        return 0;
    }
    if (steps_left = 1 && posx = 0 && posy = 2){
        c = c+1;
        return 0;
    }
    grid[posx][posy] = 1;
    // for all possible directions
    {
        solve (posx_next, posy_next, steps_left-1)
    }
    grid[posx][posy] = 0;
}

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

你的算法：

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) 运行

4

2 回答 2

0

你真的应该选择一个调试器，看看在一块小板上（2x2、3x3）发生了什么。

一个明显的问题是=分配，而不是比较。与 比较==。

还有更多的问题。找到他们。

于 2012-03-19T23:15:54.063 回答
0

这并不难，因为你已经得到了算法。为了解决这个问题，您可能需要某种动态数据结构（除非您只对 T(10,4) 的确切情况感兴趣）。对于其余部分，x 索引上的 left 是 -1，right +1，y 维度上的 down 是 -1，up +1。添加您没有访问过的边界检查和验证，工作就完成了。

但我想知道这样一个明显的算法需要多少时间。每个单元格有四种方式的决定；对于 T(10,4) 的 40 个单元格，这是 4^40 个决策。这是不可行的。诸如消除已经访问过的单元格和边界检查之类的事情消除了很多分支，但仍然......比赛的目标可能是让你找到更好的算法。

于 2012-03-19T18:55:57.597 回答