有一个m*n矩阵
。
从矩阵的一个点开始,可以移动到八个相邻点之一(上、下、左、右、左上、左下、右上、右下
)
如果一个方向上的点已经被访问过,则可以继续移动到该方向下一个未访问过的点。
您不能访问已经访问过的点,但您可以通过访问过的相邻点访问其他未访问过的点。
比如当前点是(5,5):
- 如果 (5,4) 已经被访问过,你可以移动到 (5,3)。如果 (5,3) 也被访问,则可以移动 (5,2)。
- 与对角线方向相同。如果(4,4)已经被访问过,就可以移动到(3,3)等等。
现在需要访问矩阵上的所有点,有多少种方式?
(第一个点和最后一个点可以是任意点)。
最佳答案
这类似于棋盘上的Greek-key tours数/网格上的 self 回避行走数 (see Wikipedia)。
但在您的变体中,您可以向 8 个方向移动,而不是 4 个。
对于原始版本,对于较大的 n 值似乎没有已知的公式。说明here和 here .
我实现了一个简短的 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: 很多...
关于algorithm - 有多少种方法可以访问给定矩阵的所有点?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13410168/