有多少种方法可以访问给定矩阵的所有点? [英] how many ways to visit all the points of a given matrix?
问题描述
有一个 m * n矩阵.
您可以从矩阵的一个点移至八个相邻点之一(上，下，左，右，左上，左下，右上，右下)>
如果已经访问了一个方向上的点，则可以继续移动到该方向上的下一个未访问点.
您不能访问已访问的点，但是可以通过访问的相邻点来访问其他未访问的点.
例如，当前点是(5,5):
- 如果已访问(5,4)，则可以移至(5,3).如果还访问了(5,3)，则可以移动(5,2).
- 与对角线方向相同.如果已访问(4,4)，则可以移至(3,3)，依此类推.
现在您需要访问矩阵上的所有点，有多少种方法?
(第一个点和最后一个点可以是任意点).
这类似于木板上的希腊按键游览的次数/又称为自我规避步行的次数(请参阅Wikipedia ).
但是在您的变化形式中，您可以向8个方向移动，而不是4个方向.
对于原始版本，似乎对于n的大值没有已知的公式.在此处和 从(0,0)开始的矩形网格的结果: 请注意，从不同点开始时结果会发生变化. 原始问题已修改:已添加传递.这是针对这种情况的解决方案: 从(0,0)开始的矩形网格的结果: There is a From one point of the matrix, you can move to one of the eight adjacent points ( If the point in one direction has been visited, you can continue to move to the next unvisited point in this direction. You cann't visit a point which has been visited, but you can pass through the visited adjacent point to visit other un-visited point. For example, the current point is (5,5): Now you need to visit all the points on the matrix, how many ways there are? (The first and last point can be any point). This is similar to the number of Greek-key tours on a board / AKA number of self-avoiding walks (see Wikipedia) on a grid. But in your variation, you can move to 8 directions, instead of 4. For the original version, It seems that there is no known formula for large values of n. It is explained here and here. I implemented a short C++ program to count it for your case (not the most efficient one, I guess): The results for a rectangular grid, starting from (0,0): Note that the results changes when starting from a different point. Edit: Original question was modified: pass-through was added.
Here is a solution for this case: The results for a rectangular grid, starting from (0,0): 这篇关于有多少种方法可以访问给定矩阵的所有点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
const size_t _DIM_m = 4;//colsconst size_t _DIM_n = 4;//行typedef struct//我们想按值传递数组(用于递归)，因此我们将其与struct一起包装{布尔g [_DIM_m] [_ DIM_n];} 网格;内联布尔InRange(int i，int j){return(i> = 0)&&(i< _DIM_m)&&(j> = 0)&&(j< _DIM_n);}int遍历(Grid g，int i，int j，int nVisit = 0){int nWays = 0;++ nVisit;//到目前为止已访问的点g.g [i] [j] = true;网格h = g;int i1，j1;i1 = i;j1 = j;做{--j1;} while(InRange(i1，j1)&&(g.g [i1] [j1]));;//向上(通过)如果(InRange(i1，j1))nWays + =遍历(g，i1，j1，nVisit);i1 = i;j1 = j;做{++ j1;} while(InRange(i1，j1)&&(g.g [i1] [j1]));;//向下(通过)如果(InRange(i1，j1))nWays + =遍历(g，i1，j1，nVisit);i1 = i;j1 = j;做{--i1;} while(InRange(i1，j1)&&(g.g [i1] [j1]));;//左(通过)如果(InRange(i1，j1))nWays + =遍历(g，i1，j1，nVisit);i1 = i;j1 = j;做{++ i1;} while(InRange(i1，j1)&&(g.g [i1] [j1]));;//正确(通过)如果(InRange(i1，j1))nWays + =遍历(g，i1，j1，nVisit);i1 = i;j1 = j;做{++ i1;--j1;} while(InRange(i1，j1)&&(g.g [i1] [j1]));;//右上方(通过)如果(InRange(i1，j1))nWays + =遍历(g，i1，j1，nVisit);i1 = i;j1 = j;做{--i1;++ j1;} while(InRange(i1，j1)&&(g.g [i1] [j1]));;//左下(通过)如果(InRange(i1，j1))nWays + =遍历(g，i1，j1，nVisit);i1 = i;j1 = j;做{--i1;--j1;} while(InRange(i1，j1)&&(g.g [i1] [j1]));;//左上(通过)如果(InRange(i1，j1))nWays + =遍历(g，i1，j1，nVisit);i1 = i;j1 = j;做{++ i1;++ j1;} while(InRange(i1，j1)&&(g.g [i1] [j1]));;//右下角(通过)如果(InRange(i1，j1))nWays + =遍历(g，i1，j1，nVisit);if(_DIM_m * _DIM_n == nVisit)++ nWays;//如果所有点都已访问返回nWays；} m*n Matrix.up, down, left, right, upper left, lower left, upper right, lower right)
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;
}
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;
}
