Nos dan un plano bidimensional infinito hecho de hexágonos conectados entre sí. Podemos visualizar este plano como un panal. El elemento X está presente en una de las celdas/hexágono.
Nos dan N pasos, la tarea es calcular el número de caminos hexagonales posibles en los que el elemento X tiene que realizar una caminata de N pasos y regresar al hexágono original, donde ![N\en[1, 14]](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-71fc3cf89db806c8bcd25cba7707903e_l3.png "Procesado por QuickLaTeX.com")
Ejemplos:
Input : 1 Output : Number of walks possible is/are 0 Explanation : 0 because using just one step we can move to any of the adjacent cells but we cannot trace back to the original hexagon. Input : 2 Output : Number of walks possible is/are 6 Input : 4 Output : Number of walks possible is/are 90
Acercarse :
- Una caminata hexagonal se puede definir como caminar a través de hexágonos adyacentes y regresar a la celda original. Sabemos el hecho de que un hexágono contiene seis lados, es decir, un hexágono está rodeado por seis hexágonos. Ahora, tenemos que contar el número de formas en que damos N pasos y volvemos al hexágono original.
- Ahora, supongamos que el hexágono original (donde el elemento X estaba inicialmente presente) sea el origen. Necesitamos todas las formas posibles en que podamos tomar (Nk) pasos de tal manera que tengamos algunos pasos que se remontan a nuestro hexágono original. Podemos visualizar este hexágono y su sistema de coordenadas relacionado en la imagen de abajo.
- Ahora, supongamos que nuestro elemento X estuvo presente en 0:0 de la imagen dada. Por lo tanto, podemos viajar en seis direcciones posibles desde un hexágono. Ahora, utilizando las instrucciones anteriores, memorizamos todos los movimientos posibles de modo que los rastreamos hasta el índice original de 0:0. Para memorizar, usamos una array 3D y preprocesamos nuestra respuesta para una cantidad determinada de pasos y luego consultamos en consecuencia.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción
Number of walks possible is/are 90
La complejidad temporal del código anterior es 
similar y la complejidad espacial también es similar debido a la array 3D utilizada.