可能六边形行走的计数-yiteyi-C++库

我们得到一个由六边形连接而成的无限二维平面。我们可以把这架飞机想象成蜂窝。元素X出现在其中一个单元格/六边形上。给定N个步骤，任务是计算可能的六边形路径的数量，其中元素X必须执行N个步骤的行走，然后返回到原始六边形，其中 $Nin[1, 14]$ 例如：

null

Input : 1Output : Number of walks possible is/are 0Explanation :0 because using just one step we can move toany of the adjacent cells but we cannot trace back to the original hexagon.Input : 2Output : Number of walks possible is/are 6Input : 4Output : Number of walks possible is/are 90

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法：

六边形行走可以定义为穿过相邻六边形并返回原始细胞。我们知道六边形包含六条边，即六边形被六个六边形包围。现在，我们要数一数我们走N步回到原来六边形的方法。
现在，让我们假设原始六边形（元素X最初出现的地方）是原点。我们需要所有可能的方法，我们可以采取（N-k）步骤，这样我们就有了一些可以追溯到原始六边形的步骤。我们可以从下图中看到这个六边形及其相关坐标系。

图片[2]-可能六边形行走的计数-yiteyi-C++库

现在，让我们假设，我们的元素X在给定图片的0:0处出现。因此，我们可以从六边形向六个可能的方向移动。现在，使用上面的指示，我们记住所有可能的动作，这样我们可以追溯到原始的0:0索引。为了记忆，我们使用了一个3D数组，我们对给定步骤的答案进行预处理，然后进行相应的查询。

以下是上述方法的实施情况：

C++

                         // C++ implementation of counting                       
                         // number of possible hexagonal walks                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         int                                     depth = 16;                       
                         int                                     ways[16][16][16];                       
                         int                                     stepNum;                       
           
                         void                                     preprocess(                                     int                                     list[])                       
                         {                       
                                                 // We initialize our origin with 1                       
                                                 ways[0][8][8] = 1;                       
           
                                                 // For each N = 1 to 14, we traverse in all possible                       
                                                 // direction. Using this 3D array we calculate the                       
                                                 // number of ways at each step and the total ways                       
                                                 // for a given step shall be found at                       
                                                 // ways[step number][8][8] because all the steps                       
                                                 // after that will be used to trace back to the                       
                                                 // original point index 0:0 according to the image.                       
                                                 for                                     (                                     int                                     N = 1; N <= 14; N++)                       
                                                 {                       
                                                 for                                     (                                     int                                     i = 1; i <= depth; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = 1; j <= depth; j++)                       
                                                 {                       
                                                 ways[N][i][j] = ways[N - 1][i][j + 1]                       
                                                 + ways[N - 1][i][j - 1]                       
                                                 + ways[N - 1][i + 1][j]                       
                                                 + ways[N - 1][i - 1][j]                       
                                                 + ways[N - 1][i + 1][j - 1]                       
                                                 + ways[N - 1][i - 1][j + 1];                       
                                                 }                       
                                                 }                       
           
                                                 // This array stores the number of ways                       
                                                 // possible for a given step                       
                                                 list[N] = ways[N][8][8];                       
                                                 }                       
                         }                       
           
                         // Driver function                       
                         int                                     main()                       
                         {                       
                                                 int                                     list[15];                       
                                   
                                                 // Preprocessing all possible ways                       
                                                 preprocess(list);                       
                                                 int                                     steps = 4;                       
                                                 cout <<                                     "Number of walks possible is/are "                       
                                                 << list[steps] << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java implementation of counting                       
                         // number of possible hexagonal walks                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
                                   
                                                 static                                     int                                     depth =                                     14                                     ;                       
                                                 static                                     int                                     ways[][][] =                                     new                                     int                                     [                                     16                                     ][                                     16                                     ][                                     16                                     ];                       
                                                 static                                     int                                     stepNum;                       
                                   
                                                 static                                     void                                     preprocess(                                     int                                     list[])                       
                                                 {                       
                                   
                                                 // We initialize our origin with 1                       
                                                 ways[                                     0                                     ][                                     8                                     ][                                     8                                     ] =                                     1                                     ;                       
                                   
                                                 // For each N = 1 to 14, we traverse in                       
                                                 // all possible direction. Using this 3D                       
                                                 // array we calculate the number of ways                       
                                                 // at each step and the total ways for a                       
                                                 // given step shall be found at ways[step                       
                                                 // number][8][8] because all the steps                       
                                                 // after that will be used to trace back                       
                                                 // to the original point index 0:0                       
                                                 // according to the image.                       
                                                 for                                     (                                     int                                     N =                                     1                                     ; N <=                                     14                                     ; N++)                       
                                                 {                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < depth; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j =                                     1                                     ; j < depth; j++)                       
                                                 {                       
                                                 ways[N][i][j] =                       
                                                 ways[N -                                     1                                     ][i][j +                                     1                                     ]                       
                                                 + ways[N -                                     1                                     ][i][j -                                     1                                     ]                       
                                                 + ways[N -                                     1                                     ][i +                                     1                                     ][j]                       
                                                 + ways[N -                                     1                                     ][i -                                     1                                     ][j]                       
                                                 + ways[N -                                     1                                     ][i +                                     1                                     ][j -                                     1                                     ]                       
                                                 + ways[N -                                     1                                     ][i -                                     1                                     ][j +                                     1                                     ];                       
                                                 }                       
                                                 }                       
                                   
                                                 // This array stores the number of                       
                                                 // ways possible for a given step                       
                                                 list[N] = ways[N][                                     8                                     ][                                     8                                     ];                       
                                                 }                       
                                                 }                       
                                   
                                   
                                                 /* Driver program to test above function */                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     list[] =                                     new                                     int                                     [                                     15                                     ];                       
                                   
                                                 // Preprocessing all possible ways                       
                                                 preprocess(list);                       
                                                 int                                     steps =                                     4                                     ;                       
                                                 System.out.println(                                     "Number of walks"                       
                                                 +                                     " possible is/are "                                     +                       
                                                 list[steps] );                       
                                                 }                       
                         }                       

Python3

                         # Python 3 implementation of counting                       
                         # number of possible hexagonal walks                       
           
                         depth                                     =                                     16                       
                         ways                                     =                                     [[[                                     0                                     for                                     i                                     in                                     range                                     (                                     17                                     )]                       
                                                 for                                     i                                     in                                     range                                     (                                     17                                     )]                       
                                                 for                                     i                                     in                                     range                                     (                                     17                                     )]                       
           
                         def                                     preprocess(                                     list                                     , steps):                       
                                   
                                                 # We initialize our origin with 1                       
                                                 ways[                                     0                                     ][                                     8                                     ][                                     8                                     ]                                     =                                     1                       
           
                                                 # For each N = 1 to 14, we traverse in                       
                                                 # all possible direction. Using this 3D                       
                                                 # array we calculate the number of ways                       
                                                 # at each step and the total ways for a                       
                                                 # given step shall be found at ways[step                       
                                                 # number][8][8] because all the steps after                       
                                                 # that will be used to trace back to the                       
                                                 # original point index 0:0 according to the image.                       
                                                 for                                     N                                     in                                     range                                     (                                     1                                     ,                                     16                                     ,                                     1                                     ):                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , depth,                                     1                                     ):                       
                                                 for                                     j                                     in                                     range                                     (                                     1                                     , depth,                                     1                                     ):                       
                                                 ways[N][i][j]                                     =                                     (ways[N                                     -                                     1                                     ][i][j                                     +                                     1                                     ]                                     +                       
                                                 ways[N                                     -                                     1                                     ][i][j                                     -                                     1                                     ]                                     +                       
                                                 ways[N                                     -                                     1                                     ][i                                     +                                     1                                     ][j]                                     +                       
                                                 ways[N                                     -                                     1                                     ][i                                     -                                     1                                     ][j]                                     +                       
                                                 ways[N                                     -                                     1                                     ][i                                     +                                     1                                     ][j                                     -                                     1                                     ]                                     +                       
                                                 ways[N                                     -                                     1                                     ][i                                     -                                     1                                     ][j                                     +                                     1                                     ])                       
           
                                                 # This array stores the number of ways                       
                                                 # possible for a given step                       
                                                 list                                     [N]                                     =                                     ways[N][                                     8                                     ][                                     8                                     ]                       
           
                                                 print                                     (                                     "Number of walks possible is/are"                                     ,                       
                                                 list                                     [steps])                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 list                                     =                                     [                                     0                                     for                                     i                                     in                                     range                                     (                                     16                                     )]                       
                                                 steps                                     =                                     4                       
                                   
                                                 # Preprocessing all possible ways                       
                                                 preprocess(                                     list                                     , steps)                       
                                   
                         # This code is contributed by                       
                         # Surendra_Gangwar                       

C#

                         // C# implementation of counting                       
                         // number of possible hexagonal walks                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 static                                     int                                     depth = 14;                       
                                                 static                                     int                                     [, ,]ways =                                     new                                     int                                     [16,16,16];                       
                                                 // static int stepNum;                       
                                   
                                                 static                                     void                                     preprocess(                                     int                                     []list)                       
                                                 {                       
                                   
                                                 // We initialize our origin with 1                       
                                                 ways[0,8,8] = 1;                       
                                   
                                                 // For each N = 1 to 14, we traverse in                       
                                                 // all possible direction. Using this 3D                       
                                                 // array we calculate the number of ways                       
                                                 // at each step and the total ways for a                       
                                                 // given step shall be found at ways[step                       
                                                 // number][8][8] because all the steps                       
                                                 // after that will be used to trace back                       
                                                 // to the original point index 0:0                       
                                                 // according to the image.                       
                                                 for                                     (                                     int                                     N = 1; N <= 14; N++)                       
                                                 {                       
                                                 for                                     (                                     int                                     i = 1; i < depth; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = 1; j < depth; j++)                       
                                                 {                       
                                                 ways[N,i,j] =                       
                                                 ways[N - 1,i,j + 1]                       
                                                 + ways[N - 1,i,j - 1]                       
                                                 + ways[N - 1,i + 1,j]                       
                                                 + ways[N - 1,i - 1,j]                       
                                                 + ways[N - 1,i + 1,j - 1]                       
                                                 + ways[N - 1,i - 1,j + 1];                       
                                                 }                       
                                                 }                       
                                   
                                                 // This array stores the number of                       
                                                 // ways possible for a given step                       
                                                 list[N] = ways[N,8,8];                       
                                                 }                       
                                                 }                       
                                   
                                   
                                                 /* Driver program to test above function */                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []list =                                     new                                     int                                     [15];                       
                                   
                                                 // Preprocessing all possible ways                       
                                                 preprocess(list);                       
                                                 int                                     steps = 4;                       
                                                 Console.WriteLine(                                     "Number of walks"                       
                                                 +                                     " possible is/are "                                     +                       
                                                 list[steps] );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by anuj_67.                       

Javascript

                         <script>                       
                                                 // Javascript implementation of counting                       
                                                 // number of possible hexagonal walks                       
                                   
                                                 let depth = 14;                       
                                                 let ways =                                     new                                     Array(16);                       
                                                 for                                     (let i = 0; i < 16; i++)                       
                                                 {                       
                                                 ways[i] =                                     new                                     Array(16);                       
                                                 for                                     (let j = 0; j < 16; j++)                       
                                                 {                       
                                                 ways[i][j] =                                     new                                     Array(16);                       
                                                 for                                     (let k = 0; k < 16; k++)                       
                                                 {                       
                                                 ways[i][j][k] = 0;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 let stepNum;                       
                                   
                                                 function                                     preprocess(list)                       
                                                 {                       
                                   
                                                 // We initialize our origin with 1                       
                                                 ways[0][8][8] = 1;                       
                                   
                                                 // For each N = 1 to 14, we traverse in                       
                                                 // all possible direction. Using this 3D                       
                                                 // array we calculate the number of ways                       
                                                 // at each step and the total ways for a                       
                                                 // given step shall be found at ways[step                       
                                                 // number][8][8] because all the steps                       
                                                 // after that will be used to trace back                       
                                                 // to the original point index 0:0                       
                                                 // according to the image.                       
                                                 for                                     (let N = 1; N <= 14; N++)                       
                                                 {                       
                                                 for                                     (let i = 1; i < depth; i++)                       
                                                 {                       
                                                 for                                     (let j = 1; j < depth; j++)                       
                                                 {                       
                                                 ways[N][i][j] =                       
                                                 ways[N - 1][i][j + 1]                       
                                                 + ways[N - 1][i][j - 1]                       
                                                 + ways[N - 1][i + 1][j]                       
                                                 + ways[N - 1][i - 1][j]                       
                                                 + ways[N - 1][i + 1][j - 1]                       
                                                 + ways[N - 1][i - 1][j + 1];                       
                                                 }                       
                                                 }                       
                                   
                                                 // This array stores the number of                       
                                                 // ways possible for a given step                       
                                                 list[N] = ways[N][8][8];                       
                                                 }                       
                                                 }                       
                                   
                                                 let list =                                     new                                     Array(15);                       
                                                 list.fill(0);                       
                                   
                                                 // Preprocessing all possible ways                       
                                                 preprocess(list);                       
                                                 let steps = 4;                       
                                                 document.write(                                     "Number of walks"                       
                                                 +                                     " possible is/are "                                     +                       
                                                 list[steps] );                       
                                   
                         </script>                       

输出：

Number of walks possible is/are 90

上述代码的时间复杂度为 $O(depth^3)$ 由于使用了3D阵列，空间复杂度也很相似。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章