Recuento de formas de atravesar una array según las condiciones dadas

Dado un número entero N que representa una Array Cuadrada N x N , la tarea es imprimir el número de formas de moverse desde la parte superior izquierda a la parte inferior derecha de la Array Cuadrada siguiendo las condiciones:  

• Si la posición actual del puntero está en los bordes de la array cuadrada, entonces el próximo movimiento puede ser un movimiento vertical u horizontal, cualquier cantidad de pasos (como una torre en el tablero de ajedrez).
• Si la posición actual del puntero está en las diagonales de la Array cuadrada, el próximo movimiento también debería estar en la diagonal. (Como un alfil en el tablero de ajedrez).
• Si la posición actual del puntero se encuentra en cualquier otro lugar que no sean los dos anteriores, entonces el próximo paso posible puede ser como un caballo se mueve en un tablero de ajedrez, pero la fila y la columna de la nueva posición > la fila y la columna de la antigua posición.

Ejemplos: 

Entrada: N = 2 
Salida: 3 
Explicación: 
Las tres formas posibles son: 
{0-0} – {0-1} – {1-1} 
{0-0} – {1-0} – {1-1} 
{0-0} – {1-1} 
Entrada: 3 
Salida: 18 
Explicación: 
Las formas posibles son: 
{0-0} – {2-1} – {2-2} 
{0-0} – {1- 2} – {2-2} 
{0-0} – {0-1} – {2-2} 
{0-0} – {0-1} – {0-2} – {1-2} – { 2-2} 
{0-0} – {0-1} – {0-2} – {2-2} 
{0-0} – {0-1} – {1-1} – {2-2} 
{0-0} – {0-1} – {2-1} – {2-2} 
{0-0} – {0-2} – {1-2} – {2-2} 
{0-0 } – {0-2} – {2-2} 
{0-0} – {1-0} – {2-2} 
{0-0} – {1-0} – {1-1} – {2 -2} 
{0-0} – {1-0} – {1-2} – {2-2} 
{0-0} – {1-0} – {2-0} – {2-1} – {2-2} 
{0-0} – {1-0} – {2-0} – {2- 2} 
{0-0} – {2-0} – {2-1} – {2-2} 
{0-0} – {2-0} – {2-2} 
{0-0} – {1 -1} – {2-2} 
{0-0} – {2-2} 

Enfoque: La idea es verificar recursivamente para cada caso posible si llega al final de la Array Cuadrada o no. Para ello se define una función recursiva que toma como parámetros de entrada la posición actual y la última posición. Las siguientes son las condiciones de la función recursiva:  

• Caso base: el caso base de la función es verificar si el puntero actual ha alcanzado la posición inferior derecha en la array cuadrada. Si se alcanza, entonces se incrementa la cuenta del contador que mantiene la nota del número total de vías. Si no se puede alcanzar la última posición, entonces la función debe detenerse y no debe llamarse para la siguiente iteración. Esto se implementa como:

if (cr == er && cc == ec) {
    count++;
    return;
}

if (cr > er || cc > ec) {
   return;
}

• Caso Recursivo: Dado que son posibles tres tipos de recorridos. Por lo tanto, el caso recursivo es llamar recursivamente a la función verificando si la posición actual. Si la posición actual está en los bordes de la Array cuadrada, entonces el puntero solo se puede mover horizontal o verticalmente. Y para cada recorrido vertical subsiguiente, son posibles dos opciones más de recorridos horizontales y verticales. Por lo tanto, para llevar un registro del número total de vías, ambas se llaman recursivamente en un bucle.

for (int i = 1; i <= er; i++) {
    if (cc == 0 || cr == 0 
       || cr == er || cc == ec) {
        chessboard1(cr, cc + i, er, ec);
    }
}

for (int i = 1; i <= er; i++) {
    if (cc == 0 || cr == 0 
       || cr == er || cc == ec) {
        chessboard1(cr + i, cc, er, ec);
    }
}

• Aparte de esto, si el puntero actual está en las diagonales, entonces el puntero puede moverse en diagonal. Sin embargo, para cada recorrido diagonal subsiguiente, es posible otro conjunto de diagonales subsiguientes. Por lo tanto, para realizar un seguimiento del número total de formas, se utiliza un bucle for para llamar recursivamente a la función. 
   

for (int i = 1; i <= er; i++) {
    if (cr == cc || cr + cc == er) {
        chessboard1(cr + i, cc + i,
                    er, ec);
    }
}

• Si no se cumple ninguno de los casos anteriores, entonces la siguiente posición se puede mover de tal manera que:
  • la fila nueva es > la fila anterior.
  • columna nueva > columna antigua.
• Después de ejecutar la función anterior, el valor almacenado en la variable de conteo es el número total de formas de atravesar la array cuadrada.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to count the number
// of ways to traverse the given
// N x N Square Matrix recursively
#include<bits/stdc++.h>
using namespace std;
   
// Variable to store the
// total number of ways to
// traverse the Square Matrix
     
// Function to recursively
// count the total number
// of ways to traverse the
// given N x N Square Matrix
void chessboard1(int cr, int cc,
                 int er, int ec,
                 int& count)
{
 
  // If the last index has been
  // reached, then the count is
  // incremented and returned
  if (cr == er && cc == ec)
  {
    count++;
    return;
  }
 
  // If the last index cannot
  // be reached
  if (cr > er || cc > ec)
  {
    return;
  }
 
  // If the current position is
  // neither on the edges nor
  // on the diagonal, then the
  // pointer moves like a knight
  chessboard1(cr + 2, cc + 1,
              er, ec,count);
  chessboard1(cr + 1, cc + 2,
              er, ec,count);
 
  // If the pointer is on the
  // edges of the Square Matrix
  // next move can be horizontal
  // or vertical
 
  // This for loop is used to include
  // all the horizontal traversal cases
  // recursively
  for (int i = 1; i <= er; i++)
  {
    if (cc == 0 || cr == 0||
        cr == er || cc == ec)
    {
      chessboard1(cr, cc + i,
                  er, ec,count);
    }
  }
 
  // This for loop is used to include
  // all the vertical traversal cases
  // recursively
  for (int i = 1; i <= er; i++)
  {
    if (cc == 0 || cr == 0||
        cr == er || cc == ec)
    {
      chessboard1(cr + i, cc,
                  er, ec,count);
    }
  }
 
  // If the pointer is on the
  // diagonal of the Square Matrix
  // next move is also diagonal.
  // For loop is used to include
  // all the diagonal traversal cases.
  for (int i = 1; i <= er; i++)
  {
    if (cr == cc || cr + cc == er)
    {
      chessboard1(cr + i,  cc + i, 
                  er, ec, count);
    }
  }
}
   
// Driver code
int main()
{
  int N = 3;
  int count=0;
  chessboard1(0, 0, N - 1, N - 1,count);
  cout<<count;
}
 
// This code is contributed by chahattekwani71

// Java program to count the number
// of ways to traverse the given
// N x N Square Matrix recursively
 
public class GFG {
 
    // Variable to store the total number
    // of ways to traverse the Square Matrix
    static int count = 0;
 
    // Function to recursively
    // count the total number
    // of ways to traverse the
    // given N x N Square Matrix
    public static void chessboard1(
        int cr, int cc,
        int er, int ec)
    {
 
        // If the last index has been reached, then
        // the count is incremented and returned
        if (cr == er && cc == ec) {
            count++;
            return;
        }
 
        // If the last index cannot be reached
        if (cr > er || cc > ec) {
            return;
        }
 
        // If the current position is neither
        // on the edges nor on the diagonal,
        // then the pointer moves
        // like a knight
        chessboard1(cr + 2, cc + 1, er, ec);
        chessboard1(cr + 1, cc + 2, er, ec);
 
        // If the pointer is on the
        // edges of the Square Matrix
        // next move can be horizontal or vertical
 
        // This for loop is used to include all the
        // horizontal traversal cases recursively
        for (int i = 1; i <= er; i++) {
            if (cc == 0 || cr == 0
                || cr == er || cc == ec) {
                chessboard1(cr, cc + i, er, ec);
            }
        }
 
        // This for loop is used to include all the
        // vertical traversal cases recursively
        for (int i = 1; i <= er; i++) {
            if (cc == 0 || cr == 0
                || cr == er || cc == ec) {
                chessboard1(cr + i, cc, er, ec);
            }
        }
 
        // If the pointer is on the
        // diagonal of the Square Matrix
        // next move is also diagonal.
        // For loop is used to include
        // all the diagonal traversal cases.
        for (int i = 1; i <= er; i++) {
            if (cr == cc
                || cr + cc == er) {
 
                chessboard1(cr + i,
                            cc + i,
                            er, ec);
            }
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        int N = 3;
        chessboard1(0, 0, N - 1, N - 1);
        System.out.println(count);
    }
}

# Python3 program to count the number
# of ways to traverse the given
# N x N Square Matrix recursively
 
# Variable to store the
# total number of ways to
# traverse the Square Matrix
count = 0
      
# Function to recursively
# count the total number
# of ways to traverse the
# given N x N Square Matrix
def chessboard1(cr, cc, er, ec):
  global count
  # If the last index has been
  # reached, then the count is
  # incremented and returned
  if cr == er and cc == ec:
    count+=1
    return
  
  # If the last index cannot
  # be reached
  if cr > er or cc > ec:
    return
  
  # If the current position is
  # neither on the edges nor
  # on the diagonal, then the
  # pointer moves like a knight
  chessboard1(cr + 2, cc + 1, er, ec)
  chessboard1(cr + 1, cc + 2, er, ec)
  
  # If the pointer is on the
  # edges of the Square Matrix
  # next move can be horizontal
  # or vertical
  
  # This for loop is used to include
  # all the horizontal traversal cases
  # recursively
  for i in range(1, er + 1):
    if (cc == 0 or cr == 0 or cr == er or cc == ec):
      chessboard1(cr, cc + i, er, ec)
 
  # This for loop is used to include
  # all the vertical traversal cases
  # recursively
  for i in range(1, er + 1):
    if cc == 0 or cr == 0 or cr == er or cc == ec:
      chessboard1(cr + i, cc,er, ec)
  
  # If the pointer is on the
  # diagonal of the Square Matrix
  # next move is also diagonal.
  # For loop is used to include
  # all the diagonal traversal cases.
  for i in range(1, er + 1):
    if cr == cc or (cr + cc) == er:
      chessboard1(cr + i, cc + i, er, ec)
 
N = 3
chessboard1(0, 0, N - 1, N - 1)
print(count)
 
# This code is contributed by suresh07.

// C# program to count the number
// of ways to traverse the given
// N x N Square Matrix recursively
using System;
 
class GFG{
 
// Variable to store the total number
// of ways to traverse the Square Matrix
static int count = 0;
 
// Function to recursively
// count the total number
// of ways to traverse the
// given N x N Square Matrix
public static void chessboard1(int cr, int cc,
                               int er, int ec)
{
     
    // If the last index has been reached, then
    // the count is incremented and returned
    if (cr == er && cc == ec)
    {
        count++;
        return;
    }
 
    // If the last index cannot be reached
    if (cr > er || cc > ec)
    {
        return;
    }
 
    // If the current position is neither
    // on the edges nor on the diagonal,
    // then the pointer moves
    // like a knight
    chessboard1(cr + 2, cc + 1, er, ec);
    chessboard1(cr + 1, cc + 2, er, ec);
 
    // If the pointer is on the edges
    // of the Square Matrix next move
    // can be horizontal or vertical
 
    // This for loop is used to include all the
    // horizontal traversal cases recursively
    for(int i = 1; i <= er; i++)
    {
        if (cc == 0 || cr == 0 ||
           cr == er || cc == ec)
        {
            chessboard1(cr, cc + i, er, ec);
        }
    }
     
    // This for loop is used to include all the
    // vertical traversal cases recursively
    for(int i = 1; i <= er; i++)
    {
        if (cc == 0 || cr == 0 ||
           cr == er || cc == ec)
        {
            chessboard1(cr + i, cc, er, ec);
        }
    }
     
    // If the pointer is on the
    // diagonal of the Square Matrix
    // next move is also diagonal.
    // For loop is used to include
    // all the diagonal traversal cases.
    for(int i = 1; i <= er; i++)
    {
        if (cr == cc || cr + cc == er)
        {
            chessboard1(cr + i, cc + i,
                        er, ec);
        }
    }
}
 
// Driver code
public static void Main(string[] args)
{
    int N = 3;
     
    chessboard1(0, 0, N - 1, N - 1);
     
    Console.Write(count);
}
}
 
// This code is contributed by rutvik_56

<script>
 
// Javascript program to count the number
// of ways to traverse the given
// N x N Square Matrix recursively
 
   
// Variable to store the
// total number of ways to
// traverse the Square Matrix
let count = 0
     
// Function to recursively
// count the total number
// of ways to traverse the
// given N x N Square Matrix
function chessboard1(cr, cc, er, ec)
{
 
  // If the last index has been
  // reached, then the count is
  // incremented and returned
  if (cr == er && cc == ec)
  {
    count++;
    return;
  }
 
  // If the last index cannot
  // be reached
  if (cr > er || cc > ec)
  {
    return;
  }
 
  // If the current position is
  // neither on the edges nor
  // on the diagonal, then the
  // pointer moves like a knight
  chessboard1(cr + 2, cc + 1,
              er, ec);
  chessboard1(cr + 1, cc + 2,
              er, ec);
 
  // If the pointer is on the
  // edges of the Square Matrix
  // next move can be horizontal
  // or vertical
 
  // This for loop is used to include
  // all the horizontal traversal cases
  // recursively
  for (let i = 1; i <= er; i++)
  {
    if (cc == 0 || cr == 0||
        cr == er || cc == ec)
    {
      chessboard1(cr, cc + i, er, ec);
    }
  }
 
  // This for loop is used to include
  // all the vertical traversal cases
  // recursively
  for (let i = 1; i <= er; i++)
  {
    if (cc == 0 || cr == 0||
        cr == er || cc == ec)
    {
      chessboard1(cr + i, cc,er, ec);
    }
  }
 
  // If the pointer is on the
  // diagonal of the Square Matrix
  // next move is also diagonal.
  // For loop is used to include
  // all the diagonal traversal cases.
  for (let i = 1; i <= er; i++)
  {
    if (cr == cc || cr + cc == er)
    {
      chessboard1(cr + i, cc + i, er, ec);
    }
  }
}
   
 
// Driver Code
let N = 3;
chessboard1(0, 0, N - 1, N - 1,count);
document.write(count);
 
// This code is contributed by jana_sayantan.
</script>

Producción :

18