3

有一个m*n Matrix。

从矩阵的一个点，您可以移动到八个相邻点之一 ( up, down, left, right, upper left, lower left, upper right, lower right)

如果一个方向的点已经被访问过，你可以继续移动到这个方向上的下一个未访问的点。

您不能访问已访问过的点，但可以通过已访问的相邻点访问其他未访问的点。

例如，当前点为 (5,5)：

  1. 如果 (5,4) 已被访问，您可以转到 (5,3)。如果还访问了 (5,3)，则可以移动 (5,2)。
  2. 同对角线方向。如果 (4,4) 已被访问，您可以移动到 (3,3) 等等。

现在你需要访问矩阵上的所有点，有多少种方式？

（第一个点和最后一个点可以是任意点）。

4

2 回答 2

3

这类似于棋盘上的希腊键游览次数/AKA网格上的自我回避步行次数（参见 Wikipedia ）。

但在您的变体中，您可以移动到 8 个方向，而不是 4 个。

对于原始版本，似乎没有用于较大 n 值的已知公式。这里和这里都有解释。

我实现了一个简短的 C++ 程序来计算你的情况（我猜这不是最有效的）：

const size_t _DIM_m= 4; // cols
const size_t _DIM_n= 4; // rows

typedef struct // we want to pass the array by value (for recursion), so we'll wrap it with a struct
{
    bool g[_DIM_m][_DIM_n];
} Grid;

int Traverse(Grid g, int i, int j, int nVisit= 0)
{
    int nWays= 0;

    ++nVisit;        // points visited so far
    g.g[i][j]= true;
    Grid h= g;

    // original problem:
    if (                   (0        != j) && (!g.g[i  ][j-1])) nWays+= Traverse(g, i  , j-1, nVisit); // up
    if (                   (_DIM_n-1 != j) && (!g.g[i  ][j+1])) nWays+= Traverse(g, i  , j+1, nVisit); // down
    if ((0        != i)                    && (!g.g[i-1][j  ])) nWays+= Traverse(g, i-1, j  , nVisit); // left
    if ((_DIM_m-1 != i)                    && (!g.g[i+1][j  ])) nWays+= Traverse(g, i+1, j  , nVisit); // right

    // additions for your problem:
    if ((_DIM_m-1 != i) && (0        != j) && (!g.g[i+1][j-1])) nWays+= Traverse(g, i+1, j-1, nVisit); // upper right
    if ((0        != i) && (_DIM_n-1 != j) && (!g.g[i-1][j+1])) nWays+= Traverse(g, i-1, j+1, nVisit); // lower left
    if ((0        != i) && (0        != j) && (!g.g[i-1][j-1])) nWays+= Traverse(g, i-1, j-1, nVisit); // upper left
    if ((_DIM_m-1 != i) && (_DIM_n-1 != j) && (!g.g[i+1][j+1])) nWays+= Traverse(g, i+1, j+1, nVisit); // lower right

    if (_DIM_m * _DIM_n == nVisit) ++nWays; // if all points visited
    return nWays;
}

int _tmain(int argc, _TCHAR* argv[])
{
    Grid g;

    for (size_t i= 0; i<_DIM_m; i++)
        for (size_t j= 0; j<_DIM_n; j++)
            g.g[i][j]= false;

    int nWays= Traverse(g, 0, 0); // starting point: 0, 0

    cout << nWays << endl;
    system ("pause");

    return 0;
}

从 (0,0) 开始的矩形网格的结果：

  • _DIM= 1: 1
  • _DIM= 2: 6
  • _DIM= 3: 138
  • _DIM= 4: 37948
  • _DIM= 5: 很多...

请注意，从不同的点开始时，结果会发生变化。

编辑：

修改了原始问题：添加了传递。这是针对这种情况的解决方案：

const size_t _DIM_m= 4; // cols
const size_t _DIM_n= 4; // rows

typedef struct // we want to pass the array by value (for recursion), so we'll wrap it with a struct
{
    bool g[_DIM_m][_DIM_n];
} Grid;

inline bool InRange(int i, int j)
{
    return (i >= 0) && (i < _DIM_m) && (j >= 0) && (j < _DIM_n);
}

int Traverse(Grid g, int i, int j, int nVisit= 0)
{
    int nWays= 0;

    ++nVisit;        // points visited so far
    g.g[i][j]= true;
    Grid h= g;

    int i1,j1;

    i1= i; j1= j;
    do { --j1;       } while (InRange(i1,j1) && (g.g[i1][j1]));                    // up          (pass through)
    if                       (InRange(i1,j1)) nWays+= Traverse(g, i1, j1, nVisit);

    i1= i; j1= j;
    do { ++j1;       } while (InRange(i1,j1) && (g.g[i1][j1]));                    // down        (pass through)
    if                       (InRange(i1,j1)) nWays+= Traverse(g, i1, j1, nVisit);

    i1= i; j1= j;
    do { --i1;       } while (InRange(i1,j1) && (g.g[i1][j1]));                    // left        (pass through)
    if                       (InRange(i1,j1)) nWays+= Traverse(g, i1, j1, nVisit);

    i1= i; j1= j;
    do { ++i1;       } while (InRange(i1,j1) && (g.g[i1][j1]));                    // right       (pass through)
    if                       (InRange(i1,j1)) nWays+= Traverse(g, i1, j1, nVisit);

    i1= i; j1= j;
    do { ++i1; --j1; } while (InRange(i1,j1) && (g.g[i1][j1]));                    // upper right (pass through)
    if                       (InRange(i1,j1)) nWays+= Traverse(g, i1, j1, nVisit);

    i1= i; j1= j;
    do { --i1; ++j1; } while (InRange(i1,j1) && (g.g[i1][j1]));                    // lower left  (pass through)
    if                       (InRange(i1,j1)) nWays+= Traverse(g, i1, j1, nVisit);

    i1= i; j1= j;
    do { --i1; --j1; } while (InRange(i1,j1) && (g.g[i1][j1]));                    // upper left  (pass through)
    if                       (InRange(i1,j1)) nWays+= Traverse(g, i1, j1, nVisit);

    i1= i; j1= j;
    do { ++i1; ++j1; } while (InRange(i1,j1) && (g.g[i1][j1]));                    // lower right (pass through)
    if                       (InRange(i1,j1)) nWays+= Traverse(g, i1, j1, nVisit);

    if (_DIM_m * _DIM_n == nVisit) ++nWays; // if all points visited
    return nWays;
}

从 (0,0) 开始的矩形网格的结果：

  • _DIM= 1: 1
  • _DIM= 2: 6
  • _DIM= 3: 1020
  • _DIM= 4: 8071182
  • _DIM= 5: 很多...
于 2012-11-16T13:02:25.720 回答
0

听起来像是一个典型的 TSP 问题（参见：http ://en.wikipedia.org/wiki/Travelling_salesman_problem ）。每个方框（例如 5,5）就像一个城市，只有“道路”或链接可以到达另一个节点或“城市”。希望对你有帮助

于 2012-11-16T06:57:52.373 回答