がありますm*n Matrix。
マトリックスの 1 点から、隣接する 8 点のいずれかに移動できます ( up, down, left, right, upper left, lower left, upper right, lower right) 。
ある方向のポイントが訪問済みの場合、この方向の次の未訪問ポイントに移動し続けることができます。
訪問済みのポイントを訪問することはできませんが、訪問済みの隣接するポイントを通過して、他の未訪問のポイントを訪問することができます。
たとえば、現在のポイントは (5,5) です。
次に、マトリックス上のすべてのポイントを訪問する必要があります。ウェイはいくつありますか?
(最初と最後のポイントは任意のポイントにできます)。
これは、ボード上のギリシャキーツアーの数/グリッド上の自己回避ウォーク（ウィキペディアを参照）の数に似ています。
ただし、バリエーションでは、4方向ではなく8方向に移動できます。
元のバージョンの場合、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）から始まる長方形グリッドの結果：
別のポイントから開始すると、結果が変わることに注意してください。
編集：
元の質問が変更されました：パススルーが追加されました。この場合の解決策は次のとおりです。
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）から始まる長方形グリッドの結果：
典型的な TSP の問題のように思えます (参照: http://en.wikipedia.org/wiki/Travelling_salesman_problem )。5,5 などの各ボックスは都市のようなもので、別のノードまたは「都市」に到達できる「道路」またはリンクのみがあります。それがあなたを助けることを願っています