Cuente todas las celdas visitadas posibles de un caballo después de N movimientos

Dada la posición actual de un caballo como (i, j), encuentre la cuenta de las diferentes posiciones posibles visitadas por un caballo después de N movimientos (en un tablero de 10 x 10).

Ejemplos: 

Entrada: i = 3, j = 3, n = 1 
Salida: 9 
El caballo está inicialmente en la posición [3][3]. Después de un movimiento puede visitar 8 celdas más

Entrada: i = 3, j = 3, n = 2 
Salida: 35 

Planteamiento: La idea es simple, partimos de una posición determinada, intentamos todos los movimientos posibles. Después de cada movimiento, llama recursivamente a n-1 movimientos. Tenemos que asegurarnos de no volver a visitar una celda nunca más. Hacemos una array booleana visitada que servirá como array visitada para que las posiciones no se repitan. Cuando visitamos una posición, marca esa posición como verdadera en la array.

Pasos:-  

1. Tome una array visitada booleana (10X10) e inicialice todas las celdas como falsas (no visitadas)
2. Crea dos vectores con todos los movimientos posibles de un caballo. Encontramos que hay 8 movimientos posibles de un caballo.
3. Posición válida = El caballo está dentro de los límites del tablero y la celda no está visitada.
4. Llame al método para la siguiente posición válida con n = n-1.
5. Si n == 0, regresa.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
const int N = 10;
 
// All possible moves of the knight.
 
// In X axis.
vector<int> X = { 2, 1, -1, -2, -2, -1, 1, 2 };
 
// In Y axis.
vector<int> Y = { 1, 2, 2, 1, -1, -2, -2, -1 };
 
void getCountRec(vector<vector<bool> >& board,
                 int i, int j, int n)
{
    // if n=0, we have our result.
    if (n == 0)
        return;
 
    for (int k = 0; k < 8; k++) {
        int p = i + X[k];
        int q = j + Y[k];
 
        // Condition for valid cells.
        if (p >= 0 && q >= 0
            && p < 10 && q < N) {
            board[p][q] = true;
            getCountRec(board, p, q, n - 1);
        }
    }
}
 
int getCount(int i, int j, int n)
{
    vector<vector<bool> > board(N, vector<bool>(N));
    board[i][j] = true;
 
    // Call the recursive function to mark
    // visited cells.
    getCountRec(board, i, j, n);
 
    int cnt = 0;
    for (auto row : board) {
        for (auto cell : row) {
            if (cell)
                cnt++;
        }
    }
    return cnt;
}
 
// Driver Code
int main()
{
    int i = 3, j = 3, N = 2;
    cout << getCount(i, j, N) << endl;
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG{
   
static int N = 10;
 
// All possible moves of the knight.
 
// In X axis.
static int[] X = { 2, 1, -1, -2, -2, -1, 1, 2 };
 
// In Y axis.
static int[] Y = { 1, 2, 2, 1, -1, -2, -2, -1 };
 
static void getCountRec(boolean[][] board,
                        int i, int j, int n)
{
     
    // If n=0, we have our result.
    if (n == 0)
        return;
 
    for(int k = 0; k < 8; k++)
    {
        int p = i + X[k];
        int q = j + Y[k];
 
        // Condition for valid cells.
        if (p >= 0 && q >= 0 &&
            p < 10 && q < N)
        {
            board[p][q] = true;
            getCountRec(board, p, q, n - 1);
        }
    }
}
 
static int getCount(int i, int j, int n)
{
    boolean[][] board = new boolean[N][N];
    board[i][j] = true;
 
    // Call the recursive function to mark
    // visited cells.
    getCountRec(board, i, j, n);
 
    int cnt = 0;
    for(boolean[] row : board)
    {
        for(boolean cell : row)
        {
            if (cell != false)
                cnt++;
        }
    }
    return cnt;
}
 
// Driver code
public static void main(String[] args)
{
    int i = 3, j = 3, N = 2;
     
    System.out.println(getCount(i, j, N));
}
}
 
// This code is contributed by sanjoy_62

# Python program for the above approach
SIZE = 10
 
# All possible moves of the knight.
# In X axis.
X = [2, 1, -1, -2, -2, -1, 1, 2]
 
# In Y axis.
Y = [1, 2, 2, 1, -1, -2, -2, -1]
 
def getCountRec(board, i, j, n):
     
    # If n=0, we have our result.
    if n == 0:
        return
     
    for k in range(8):
        p = i + X[k]
        q = j + Y[k]
         
        # Condition for valid cells.
        if p >= 0 and q >= 0 and p < 10 and q < SIZE:
            board[p][q] = True
            getCountRec(board,p,q,n-1)
     
def getCount(i, j, n):
    board = [[False for i in range(SIZE)] for j in range(SIZE)]
    board[i][j] = True
     
    # Call the recursive function to mark
    # visited cells.
    getCountRec(board, i, j, n)
    cnt = 0
     
    for row in board:
        for cell in row:
            if cell != False:
                cnt += 1
             
    return cnt
 
# Driver code   
i = 3
j = 3
N = 2
print(getCount(i, j, N))
 
# This code is contributed by rdtank.

// C# program for the above approach
using System;
class GFG
{
 
  static int N = 10;
 
  // All possible moves of the knight.
 
  // In X axis.
  static int [] X = { 2, 1, -1, -2, -2, -1, 1, 2 };
 
  // In Y axis.
  static int [] Y = { 1, 2, 2, 1, -1, -2, -2, -1 };
 
  static void getCountRec(bool[,] board,
                          int i, int j, int n)
  {
 
      // If n=0, we have our result.
      if (n == 0)
          return;
 
      for(int k = 0; k < 8; k++)
      {
          int p = i + X[k];
          int q = j + Y[k];
 
          // Condition for valid cells.
          if (p >= 0 && q >= 0 &&
              p < 10 && q < N)
          {
              board[p, q] = true;
              getCountRec(board, p, q, n - 1);
          }
      }
  }
 
  static int getCount(int i, int j, int n)
  {
      bool [, ] board = new bool[N, N];
      board[i, j] = true;
 
      // Call the recursive function to mark
      // visited cells.
      getCountRec(board, i, j, n);
 
      int cnt = 0;
      foreach(bool cell in board)
      {
          if(cell != false)
            cnt++;
      }
      return cnt;
  }
 
  // Driver code
  public static void Main()
  {
      int i = 3, j = 3, N = 2;
 
      Console.WriteLine(getCount(i, j, N));
  }
}
 
// This code is contributed by ihritik

<script>
 
// JavaScript implementation of the approach
const SIZE = 10;
 
// All possible moves of the knight.
 
// In X axis.
let X = [ 2, 1, -1, -2, -2, -1, 1, 2 ];
 
// In Y axis.
let Y = [ 1, 2, 2, 1, -1, -2, -2, -1 ];
 
function getCountRec(board,i,j,n)
{
    // if n=0, we have our result.
    if (n == 0)
        return;
 
    for (let k = 0; k < 8; k++) {
        let p = i + X[k];
        let q = j + Y[k];
 
        // Condition for valid cells.
        if (p >= 0 && q >= 0
            && p < 10 && q < SIZE) {
            board[p][q] = true;
            getCountRec(board, p, q, n - 1);
        }
    }
}
 
function getCount(i, j, n)
{
    let board = new Array(SIZE).fill(0).map(()=>new Array(N));
    board[i][j] = true;
 
    // Call the recursive function to mark
    // visited cells.
    getCountRec(board, i, j, n);
 
    let cnt = 0;
    for (let row of board) {
        for (let cell of row) {
            if (cell)
                cnt++;
        }
    }
    return cnt;
}
 
// Driver Code
 
let i = 3, j = 3,N = 2;
document.write(getCount(i, j, N),"</br>");
 
 
// This code is contributed by shinjanpatra
 
</script>// JavaScript implementation of the approach
 
const SIZE = 10;
 
// All possible moves of the knight.
 
// In X axis.
let X = [ 2, 1, -1, -2, -2, -1, 1, 2 ];
 
// In Y axis.
let Y = [ 1, 2, 2, 1, -1, -2, -2, -1 ];
 
function getCountRec(board,i,j,n)
{
    // if n=0, we have our result.
    if (n == 0)
        return;
 
    for (let k = 0; k < 8; k++) {
        let p = i + X[k];
        let q = j + Y[k];
 
        // Condition for valid cells.
        if (p >= 0 && q >= 0
            && p < 10 && q < SIZE) {
            board[p][q] = true;
            getCountRec(board, p, q, n - 1);
        }
    }
}
 
function getCount(i, j, n)
{
    let board = new Array(SIZE).fill(0).map(()=>new Array(N));
    board[i][j] = true;
 
    // Call the recursive function to mark
    // visited cells.
    getCountRec(board, i, j, n);
 
    let cnt = 0;
    for (let row of board) {
        for (let cell of row) {
            if (cell)
                cnt++;
        }
    }
    return cnt;
}
 
// Driver Code
 
let i = 3, j = 3,N = 2;
document.write(getCount(i, j, N),"</br>");
 
// This code is contributed by shinjanpatra
</script>

35